如何做到位操作，当你不知道在哪里最左边的“1”位？ [英] How to do the bit manipulation when you don't know where the left-most '1' bit is?

问题描述

0000 => 0000
0001 => 1111
0010 => 1110
0100 => 1100
1000 => 1000

还有：

0101 => 1101

正如你所看到的，我需要填补在最后1的'1'，但我不知道提前其中最后一个'1'。

As you can see I need to fill with '1's after the last '1', but I do not know in advance where the last '1' is.

推荐答案

被打开，很容易使位的面具，应该是不变的（不是真的，但它更容易解释这种方式）：最左边的1复制到所有位，它的右侧：

Instead of directly making the mask of the bits that have to be switched on, it's easier to make the mask of bits that should be unchanged (not really, but it's easier to explain this way): copy the left-most 1 to all bits to the right of it:

m = x | (x >> 1);
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;   // 5 steps for 32 bits, in general log2(width) steps

例如， 0101 =＆GT; 0111 或 1000 - ＆GT; 1111 。

显然那补是应该被打开（除非 X 为零）位的面具，所以现在：

Clearly the complement of that is the mask of bits that should be turned on (unless x was zero), so now:

if (x != 0)   // this line makes me sad :(
    x |= ~m;

避免长循环，但仍具有在它的一部分是不严格的位操作

Avoids a long loop, but still has a part in it that isn't strictly bit-manipulation.

少清晰，使用的伎俩，从我的意见，观察，如果 M 只有它的最左边1套，它的否定将是在要设置的位 X （这已经在设置X ，但没关系位）。所以，你得到：

Less clearly, using the trick from my comment, observe that if m only had its left most 1 set, its negation would be the bits that have to be set in x (and a bit that is already set in x, but that's ok). So you get:

m &= ~(m >> 1);  // see below
x |= -m;

的 M＆安培; =〜（M＆GT;＆GT; 1）招只需要最左边的1 M ，这现在是可能的，因为 M 是两个零下1的动力，因此，只有1，可以有一个0到左边的是最左边1.在的情况下，X = 0 ， M = 0 ，因此显然 M＆安培;东西= 0 - 无需特殊情况。在当X 的最高位设置，从而 M = -1 ，虽然没有零到留下最左边的1，它被转移由右移反正（确保它是一个合乎逻辑的转变，而不是一个算术移位）。

The m &= ~(m >> 1) trick takes only the leftmost 1 of m, this is possible now because m is a power of two minus 1, so the only 1 that can have a 0 to the left of it is the leftmost 1. In the case of x = 0, m = 0 and therefore obviously m & something = 0 - no special case required. In the case that x has the top bit set and thus m = -1, while there is no zero to the left of the leftmost 1, it gets shifted in by the right shift anyway (make sure it's a logical shift, not an arithmetic shift).

这篇关于如何做到位操作，当你不知道在哪里最左边的“1”位？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！