使用仅按位运算符创建一个标记最重要设置位的掩码

Question

这是昨晚应该给我的一个更大的编程任务的一部分.无法弄清楚这个问题,但我很好奇它是如何解决的.

该函数int greatestBitPos(int x)应返回一个标记最高位的位置的int掩码.如果x == 0,则返回0.不允许控制结构(if,while,？:).

例: greatestBitPos(96) = 0x40

合法经营者:!〜&^ | + << >> =

这个关于位杂乱的网站是我用作起点的东西,特别是第二种算法.但是,它使用<比较,这个问题不允许.

欢迎所有的想法,谢谢!

编辑:请假设2的补码,32位整数.对于所有负数,它们的最高位设置,因此返回值应为0x80000000.

Answer 1

更新为负数工作(假设这应该返回,0x80000000因为这些数字的顶部位设置)

int gbp(int n) {
 // return log(2) of n
 unsigned int m;
 m = n;
 m = m | m >> 1;
 m = m | m >> 2;
 m = m | m >> 4;
 m = m | m >> 8;
 m = m | m >> 16;
 m = m & ((~m >> 1)^0x80000000);
printf("m is now %d\n", m);
return m;
}

说明:

从任何位模式开始,当我们向右移动1并取OR时,相邻位将变为1

00010100
00001010
--------
00011110

你重复这个,直到你在前导数字的右边都有一个,通过连续移动2,4,8,16(如果你有32位数字;对于更大的int你继续前进).

最后你需要通过反转数字来"去除所有其他的",右移1,然后取AND:

00011111 AND 11110000 = 00010000

你有它.

对于负数,最终操作可确保您不会杀死最高位(如果存在).如果你想用负数做其他事情,请告诉我它是什么.