побитовый самый значительный установленный бит

Question

Я хочу найти самый значимый бит, установленный на 1.Я перепробовал все возможные пути от & до ИЛИ всех битов от 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 для 1 и 6 для 64 (1000000 в двоичном виде). Вы можете настроить это, если хотите. Также обратите внимание, что я использовал оператор без знака справа, а не смещение вправо со знаком. Это связано с тем, что целью здесь является работа с необработанными битами, а не их подписанная интерпретация, но в данном случае это не имеет значения, поскольку все отрицательные значения завершатся в первой итерации цикла до того, как произойдет смещение.

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

Answer 6

Для формата Little Endian:

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

Answer 7

Просто используйте метод numberOfTrailingZeros (значение) класса Long или Integer.

Answer 8

Просто чтобы добавить еще один подход

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

Answer 9

Не самый эффективный, возможно, но это должно работать ::

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

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;