2007年五月月 发布的文章

数的圆整算式

一般在考虑到内存对齐的程序里面势必要使用数的圆整算式,一般来说在计算机程序里一般都是圆整到2的次幂上,而很多书上也有很多基于'移位'操作的圆整到2的次幂上的算法公式,形式都是很简单的,很实用。

这里要说的是一个圆整到任意正整数(n > 1,圆整到1没有必要^_^)的算式,突然觉得如果说算法有些大了。我们来推导一下,也不是严密推导。就是怎么想的怎么说。

如果有两个正整数a、b,其中a >= 1, b > 1,求a圆整于b后的结果?

这里不妨考虑三种情况:
(1) a = b
毫无疑问结果应该就是b;

(2) a > b
a > b > 1 => a/b >= 1(计算机语言中的a/b) => 圆整结果为(a/b + 1) * b;—(1)

(3) a < b
1 =< a a/b = 0 (计算机语言中的a/b) => 圆整结果为b (0 + 1) * b => (a/b + 1) * b。—(2)

从上面式子可以看出当a b时可以统一成(a/b + 1) * b,但是a = b时 (a/b + 1) *b = 2b显然和正确结果b不符。这时如何统一算式呢?我们从条件考虑:
假设我们现在有一个x = a – 1 > b > 1,从x > b我们可以通过代入上面的公式(1)得出圆整结果:(x/b + 1) * b,这里a有了更严格的限制 a > 2;同样有一个 1 =< x = a – 1 = 2了。

由上面两个结果,可以推出另一个形式的圆整算式: ((a – 1)/b + 1) * b,它对于(a >=2,b > 1成立)
那么当1 =

这样((a – 1)/b + 1) * b对于a >=1,b >1就都成立了,这个算式形式就统一了^_^。

#define ROUNDTO(a, boundary) ((((a) – 1)/(boundary) + 1) * (boundary))

//测试一下
std::cout << ROUNDTO(1, 2) 输出结果:
2
3
21
7

C++咬文嚼字-'Pointer Trick'

晚上饭后抽空看了看如何实现一个内存管理器,涉及内存操作必定少不了指针,恰研究到offsetof这个operator,也看了它的实现,顿有所悟。

先看一段代码:
struct Foo {
        int     a;
        char*   p;
        char    b;
};

Foo* p1 = reinterpret_cast(0);
Foo* p2 = 0;

bool b = (p1 == p2);
std::cout << b << std::endl;

输出结果:
1

请考虑一下虽然打印出来的结果是:1,但是这两个赋值语句的意义相同吗???

Foo* p2 = 0;
相信所有C++的初学者都知道,这句的意思是p2是一个空指针,或者说p2尚未指向任何对象。

Foo* p1 = reinterpret_cast(0);
那么这句呢?难道p1也是如p2一样,是一个空指针么?

我们再回顾一下一般我们给指针赋值都是如何做的:
Foo* p = new Foo();

Foo aFoo;
Foo *p = &aFoo;

无论是new Foo()还是&aFoo,实际上他们返回的都是一个地址常量,类似于0xffbff204这样的地址值,我们就不妨假设new Foo()或&aFoo返回的地址常量值就为0xffbff204。

继续!我们将如何解释一个指针呢?在Stanley B. Lippman的鸿篇巨制'C++ Primer 3rd'中的第3.3小节有这样的叙述:
每个指针都有一个相关的类型。… … 指针的类型可以指示编译器怎样解释特定地址上内存的内容以及该内存区域应该跨越多少内存单元。

好了,我们解释一下Foo *p = 0xffbff204; (或Foo *p = (Foo*)0xffbff204 或Foo *p = reinterpret_cast(0xffbff204) 更好一些,因为Foo *p = 0xffbff204;这样的语句在C++中很可能不能通过编译,并提示'invalid conversion from `unsigned int' to `Foo*'之类的错误')
我们有这样一个Foo类型的指针,其指向一个起始地址为0xffbff204的类型为Foo的对象,这样我们可以通过&(p->b)得到b的地址:即在0xffbff204的基础上再加上成员b在结构体中的偏移量,如偏移量是8,我们得到的b的地址就是0xffbff204 + 8d。

现在我们把0xffbff204换成了0,也就是Foo* p1 = reinterpret_cast(0); 其实我们再告诉编译器:我们有这样一个Foo类型的指针,其指向一个起始地址为0×0的类型为Foo的对象。这时如果我们想得到b的地址,我们一样可以通过&(p->b)获得,即在0×0的基础上再加上成员b在结构体中的偏移量,如偏移量是8,我们得到的b的地址就是0×0+ 8d = 8,其实这就是b在结构体里面的偏移量。

有些人一直在担心,p1指向地址为0处,一旦引用p1会不会出问题,请牢记这里我们并没有做dereference操作,即*p操作,而且获取b的地址实际上编译器是通过p1以及b的偏移量来计算得来的,也不涉及到dereference操作。你也可以理解为有一个'虚拟'的Foo object就存储在0×0这个地址上,呵呵。越过脑子中的那个阴影向前一步便会豁然开朗。

不进一步分析了,一般offsetof的实现如下:
#define offsetof(type, f) ((size_t)((char *)&((type *)0)->f – (char *)(type *)0))
有了上面的阐述相信理解这个宏定义应该不难。

用C++的写法:std::cout << reinterpret_cast<size_t>(&((reinterpret_cast<Foo*>(0))->p)) << std::endl;
不知道上面我的逻辑是否适合大家。^_^

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! 图片广告位1 图片广告位2 图片广告位3 商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats