问个BITWISE的题目。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个BITWISE的题目。

问个BITWISE的题目。# JobHunting - 待字闺中

C*n2011-09-29 07:09

1 楼

The following function will return true for some numbers and false for other
numbers. Explain which ones.
unsigned int BLACKBOX(unsigned int x) { return (x)&((x)-1)); }

c*p2011-09-29 07:09

2 楼

如果x是2的整数幂，返回1；否则返回0。
很常用并且好用的一个宏，谁用谁知道。

other

【在 C*******n 的大作中提到】

: The following function will return true for some numbers and false for other
: numbers. Explain which ones.
: unsigned int BLACKBOX(unsigned int x) { return (x)&((x)-1)); }
:

C*n2011-09-29 07:09

3 楼

能给简单解释下么大牛？

【在 c****p 的大作中提到】

: 如果x是2的整数幂，返回1；否则返回0。
: 很常用并且好用的一个宏，谁用谁知道。
:
: other

c*p2011-09-29 07:09

4 楼

oops，把结果说反了。
考虑两个二进制数：
a = 1000, b = 1010;
a&(a-1) = 1000 & 0111 = 0000;
b&(b-1) = 1010 & 1001 = 0001;
证明过程我的思路是这样，假设一个数x可以表示成x = 2^k + n的形式，
其中　2^k <= x < 2^(k+1)。
若n不为0，则x - 1 = 2^k + n - 1，则 x & (x - 1) = (2^k & 2^k) + (n&(n-1))，结
果非0；
若n为0，则x - 1 = 2^k - 1 = sum(2^(k-1)+2^(k-2)...+2^0) = n'，
则x & (x-1) = (1*2^k & 0*2^k) + (0 & n') = 0;

【在 C*******n 的大作中提到】

: 能给简单解释下么大牛？

C*n2011-09-29 07:09

5 楼

多谢朋友！