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

这是我昨晚为我设计的一个较大的编程任务的一部分。无法弄清楚这个问题，但我很好奇它是如何解决的。创建一个掩码，标记最重要的设置位，只使用按位运算符

函数int greatestBitPos(int x)应该返回一个int掩码，它标记最高有效位的位置。如果x == 0，则返回0.没有控制结构（如果，但是，？:)允许。

例子：greatestBitPos(96) = 0x40

合法经营！〜&^| + < < >> =

This website on bit twiddling是我用作起点的东西，特别是第二种算法。但是，它使用<比较，这个问题不允许。

欢迎任何想法，谢谢！

编辑：请假设2的补码，32位整数。对于所有负数，它们都设置了最高位，所以返回值应该是0x80000000。

来源

2014-01-28 rywhite

SergeyL：这太糟糕了，你删除了你的答案。你可以写'+〜0'而不是'-1'并且说“这个假设是2的补码”。 – 2014-01-28 18:20:46

两个补码是正确的假设。我将编辑该问题。 – rywhite

@ H2CO3不是我删除它的原因。它返回除了最低有效集之外的所有比特。 –

更新为负数（假设这应该返回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右移，并采取与“去除所有其他的人”：

00011111 AND 11110000 = 00010000

和你有它。

对于负数，最后的操作可以确保您不会杀掉顶部位（如果存在）。如果你想用负数来做其他事情，请告诉我它是什么。

来源

2014-01-28 18:30:36 Floris

还有'| ='和'＆='操作符。 – 2014-01-28 18:32:04

非常优雅，我喜欢。 – rywhite

@ H2CO3 - 是的，这可能会稍微收紧一点。不确定它会非常影响执行时间。在这样的情况下，我更喜欢密度的清晰度 - 但这是个人的事情。 – Floris

填充所有的位到最显著一个的右边的通过移位和的OR'ing：

0b 0010 0000 0000 0000 0100 0000 0000 0000 
0b 0011 0000 0000 0000 0110 0000 0000 0000 
0b 0011 1100 0000 0000 0111 1000 0000 0000 
0b 0011 1111 1100 0000 0111 1111 1000 0000 
0b 0011 1111 1111 1111 1111 1111 1111 1111

然后右移，并添加1离开最显著之一：

0b 0001 1111 1111 1111 1111 1111 1111 1111 
0b 0010 0000 0000 0000 0000 0000 0000 0000

代码：

int greatestBitPos(int x) { 
    int is_nonzero = (x != 0); 
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 18); 
    x = x | (x >> 16); 
    return (is_nonzero * ((x >> 1) + 1)); 
}

来源

2014-01-28 18:31:34 Lynn

我很喜欢这个主意。但是，这个问题不允许使用'*'或'！='运算符。 – rywhite

我喜欢'向右移位并加上一个'来获得最高位。比我的解决方案更优雅。 – Floris

我仍然很想看看其他人能想出什么，但一个朋友已经找出答案。

int greatestBitPos(int x) { 
    int a = x | (x >> 1); 
    a = a | (a >> 2); 
    a = a | (a >> 4); 
    a = a | (a >> 8); 
    a = a | (a >> 16); 
    return ((a^(a >> 1)) | 0x80 << 24) & a; 
}

知道，如果我们能所有位设置为MSB权为1，那么就很容易刚才设置的MSB和其他位。这个答案也适用于否定（关于二进制补码）。

来源

2014-01-28 18:31:42 rywhite

事实上，可以使用有提到的第二算法，有轻微的修改：

在b存在形式0 ^Ñ米

(a > b) == !!(a & ~b)

的的特殊情况下成立。

来源

2014-01-28 18:36:09

assign a_reversed = {<<{a}}; 
assign a_2s_compl = (~a_reversed) + 1'b1; 
assign a_lsb_set = a_reversed & a_2s_compl; 
assign a_msb_set = {<<{a_lsb_set}};

这可能都在一行，并在参数化的功能来完成，但我已经把所有的步骤，这里要说明的明确什么在每一步发生。

来源

2016-08-19 00:27:09 stephann

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

回答

相关问题