按位最高有效位设置位

Question

我想找到设置为1的最高位。我已经尝试了从&到对所有位进行OR操作的所有可能方法，但都没有成功。

例如，如果是1000000，我希望得到7。

- mkuk

---

你详细尝试了什么？结果是什么？ - user647772

我已经完成了所有的 count += 1&(~x >> 1-31);，但它给出的数字与我的预期不同。我只想要最高位为1的位。 - mkuk

负数应该如何处理？ - Ted Hopp

不需要在意具体数值，我只需要最高位是1的那一位。所以即使是-2，我仍然需要最高位是1的那一位。 - mkuk

Answer 1

你需要像这样使用32 - Integer.numberOfLeadingZeros(value)。

参考链接：http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Integer.html#numberOfLeadingZeros%28int%29。

- zch

Answer 2

我遇到的最流畅的实现方式 - 三次迭代和表查找。

unsigned int msb32(unsigned int x)
{
    static const unsigned int bval[] =
    { 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 };

    unsigned int base = 0;
    if (x & 0xFFFF0000) { base += 32/2; x >>= 32/2; }
    if (x & 0x0000FF00) { base += 32/4; x >>= 32/4; }
    if (x & 0x000000F0) { base += 32/8; x >>= 32/8; }
    return base + bval[x];
}

- JJWalker

Answer 3

虽然已经有了一个被接受的答案，但我有另外一种方法，我认为这种方法更容易。

如果你想使用位运算，这就是方法。基本上，我将整数向右移位直到它变成零。不需要任何掩码。

private static int mostSignificantBit(int myInt){
    int i = 0;
    while (myInt != 0) {
        ++i;
        myInt >>>= 1;
    }
    return i;
}

另一种方法是通过数学计算来得出结果：

private static int mostSignificantBit(int myInt){
    if (myInt == 0) return 0;    // special handling for 0
    if (myInt < 0) return 32;    // special handling for -ve

    return (int)(Math.log(myInt)/Math.log(2)) +1;
}

- Adrian Shum

Answer 4

如果你坚持要直接使用位运算符，可以尝试以下方法：

private int mostSignificantBit(int myInt){
  int mask = 1 << 31;
  for(int bitIndex = 31; bitIndex >= 0; bitIndex--){
    if((myInt & mask) != 0){
      return bitIndex;
    }
    mask >>>= 1;
  }
  return -1;
}

我们将掩码初始化为1 << 31，因为这表示一个后跟31个0的1。我们使用该值来测试索引31（第32个位置）是否为1.当我们将此值与myInt进行and时，除非在myInt中设置了相应的位，否则我们得到0。如果是这种情况，则返回bitIndex。如果不是，则将掩码向右移动1次并重试。我们重复直到没有地方可以移动为止，在这种情况下，它意味着没有任何位被设置（也许你想在这里抛出异常而不是返回-1）。

请注意，这将返回值 0 以及 6 的值，用于 64 （二进制中的 1000000 ）。如果您愿意，可以进行调整。还要注意，我使用了无符号右运算符而不是有符号右移。这是因为这里的意图是处理原始位而不是它们的有符号解释，但在这种情况下并不重要，因为所有负值在移位发生之前都会在循环的第一次迭代中终止。

- Michael McGowan

---

实际上，使用无符号右移操作符非常重要。如果myInt不是负数，则需要将mask进行移位，而它最初是负值。 - Ted Hopp

你说得对，如果使用有符号右移（因为mask一开始是负数），mask始终会有一个不属于它的前导1。然而，这并不影响我的实现结果，因为当myInt不是负数时，多余的1位总是被与0（即myInt的符号位，我们刚刚说过是正数）进行“与”操作。 - Michael McGowan

好观点！我没有考虑到在“掩码”中有前导1的后果，正如你所指出的那样，这些1实际上什么也不代表。 - Ted Hopp

Answer 5

连续逼近法可以将迭代次数最小化为五次循环：

unsigned int mostSignificantBit(uint32_t val) {
  unsigned int bit = 0;

  /* 4 = log(sizeof(val) * 8) / log(2) - 1 */
  for(int r = 4; r >= 0 ; --r) {
    unsigned shift = 1 << r; /* 2^r */
    uint32_t sval = val >> shift;
    if (sval) {
        bit += shift;
        val = sval;
    }
  }
  return bit;
}

- D Lindsey

Answer 6

也许不是最高效的方法，但这应该可以工作：

public int firstBit(int i) {
    return i < 0 ? 31 : i == 0 ? 0 : Integer.toString(i, 2).length();
}

- Ted Hopp

---

不行，绝对不可以。虽然它可以工作，但是效率太低了，真令人痛心。 - Stefan Reich

Answer 7

只是想再提供另一种方法

public static int mostSignificantBit(int b) {
    for (int i = 1 << 30, j = 0; i > 0; i /= 2, j++) {
           if ((b & i) > 0) {
            return 31-j;
        }
    }
    return -1;
}

- Johan Sjöberg

---

你可能想要输入一个 int 而不是一个 byte。 - Michael McGowan

我认为你的起点不正确。这段代码对于Integer.MAX_VALUE和负数给出了相同的答案。 - Michael McGowan

Answer 8

只需使用Long或Integer类的numberOfTrailingZeros（value）方法。

- quit

Answer 9

对于小端模式：

((yourByte & yourBitMask) >> msbIndex) && 0x01

- Bavithra Thangaraj

Answer 10

if( value | 0x40 ) return 7;
else if( value | 0x20 ) return 6;
else if( value | 0x10 ) return 5;
else if( value | 0x8 ) return 4;
else if( value | 0x4 ) return 3;
else if( value | 0x2 ) return 2;
else if( value | 0x1 ) return 1;

- user1185840

---

返回第8到31个的情况发生了什么？ - Ted Hopp