按位最重要的设置位

Question

我想找到设置的最重要的位1.我已经尝试了从&OR到OR的所有可能的方式1,31并且它不起作用.

就像1000000我想拥有的一样7.

Answer 1

http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Integer.html#numberOfLeadingZeros%28int%29 你想要类似的东西32 - Integer.numberOfLeadingZeros(value).

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];
}

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;
}

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因为它代表 1 后跟 31 个 0。我们使用该值来测试索引 31（第 32 个位置）是否为 1。当我们and将此值与 一起使用时myInt，除非在 中设置了相应的位，否则我们会得到 0 myInt。如果是这种情况，我们将返回该bitIndex。如果不是，那么我们将掩码向右移动 1，然后重试。我们重复直到用完要移动的位置，在这种情况下，这意味着没有设置任何位（也许您想在此处抛出异常而不是返回 -1）。

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