Количество битов, используемых в int

Question

Если у вас есть двоичное число 10110, как я могу получить его, чтобы вернуть 5? например, число, которое говорит, сколько битов используется? Ниже приведены некоторые примеры:

• 101 должен вернуть 3
• 000000011 должен вернуть 2
• 11100 должен вернуть 5
• 101010101 должен вернуть 9

Как это можно получить самым простым способом на Java? Я придумал следующий метод, но могу ли я сделать это быстрее:

public static int getBitLength(int value)
{
    if (value == 0)
    {
        return 0;
    }
    int l = 1;
    if (value >>> 16 > 0) { value >>= 16; l += 16; }
    if (value >>> 8 > 0) { value >>= 8; l += 8; }
    if (value >>> 4 > 0) { value >>= 4; l += 4; }
    if (value >>> 2 > 0) { value >>= 2; l += 2; }
    if (value >>> 1 > 0) { value >>= 1; l += 1; }
    return l;
}

Answer 1

легкий

32 - Integer.numberOfLeadingZeros(value)

Если вы ищете алгоритмы, разработчики Java API соглашаются с вашим подходом разделения битов «разделяй и властвуй»:

public static int numberOfLeadingZeros(int i) {
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

Редактировать : В качестве напоминания для тех, кто верит в точность вычислений с плавающей запятой, запустите следующий тестовый комплект:

public static void main(String[] args) {
    for (int i = 0; i < 64; i++) {
        long x = 1L << i;
        check(x);
        check(x-1);
    }
}

static void check(long x) {
    int correct = 64 - Long.numberOfLeadingZeros(x);
    int floated = (int) (1 + Math.floor(Math.log(x) / Math.log(2)));
    if (floated != correct) {
        System.out.println(Long.toString(x, 16) + " " + correct + " " + floated);
    }
}

Первое обнаруженное отклонение:

ffffffffffff 48 49

Answer 2

К сожалению, нет Integer.bitLength() метода, который бы дал вам ответ напрямую.

Аналогичный метод существует для BigInteger, поэтому вы можете использовать его:

BigInteger.valueOf(value).bitLength()

Создание объекта BigInteger сделает его несколько менее эффективным, но это будет иметь значение, только если вы сделаете это много миллионов раз.

Answer 3

Вы хотите вычислить логарифм числа 2 для базы, а именно:

1 + floor(log<sub>2</sub>(value))

В Java есть метод Math.log, который использует базу e, поэтому вы можете сделать:

1 + Math.floor(Math.log(value) / Math.log(2))

Answer 4

Начиная с здесь , способ сделать это с помощью только побитового ввода и сложения:

int GetHighestBitPosition(int value) {
  if (value == 0) return 0;

  int position = 1;
  if ((value & 0xFFFF0000) == 0) position += 16;
  if ((value & 0xFF00FF00) == 0) position += 8;
  if ((value & 0xF0F0F0F0) == 0) position += 4;
  if ((value & 0xCCCCCCCC) == 0) position += 2;
  if ((value & 0xAAAAAAAA) == 0) position += 1;

  return position;
}

Answer 5

Вы действительно просто хотите найти позицию старшего бита, равного 1. См. эту страницу , под заголовком «Поиск целочисленной лог-базы 2 целого числа (или позиции старшего бита набор)».

Answer 6

Будьте осторожны с тем, что вы просите. Один из очень быстрых методов - сделать поиск по таблице:

int bittable [] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ... };
int numbits (int v)
{
    return bittable [v];
}

где bittable содержит запись для каждого int. Конечно, это имеет осложнения для отрицательных значений. Более практичным способом было бы подсчитать биты в битовых полях числа

int bittable [16] = {0, 1, 1, 2,  1, 2, 2, 3,  1, 2, 2, 3,  2, 3, 3, 4};
int numbits (int v)
{
    int s = 0;
    while (v != 0)
    {
         s += bittable [v & 15];
         v >>= 4;
    }
    return s;
}

Answer 7

Другое решение заключается в использовании length() из BitSet, который в соответствии с API

Возвращает "логический размер" ... индекс старший установленный бит ... плюс один.

Чтобы использовать BitSet, вам нужно создать массив. Так что это не так просто, как начать с чистого int. Но вы получаете его из коробки JDK - протестировано и поддерживается. Это будет выглядеть так:

  public static int bitsCount(int i) {
    return BitSet.valueOf(new long[] { i }).length();
  }

Применительно к примерам в вопросе:

  bitsCount(0b101); // 3
  bitsCount(0b000000011); // 2
  bitsCount(0b11100); // 5
  bitsCount(0b101010101); // 9

При запросе битов BitSet представляется мне подходящей структурой данных.

Answer 8

Integer.toBinaryString (значение) .length ()

Answer 9

Если вы ищете самый быстрый (и без стола, который, безусловно, быстрее), это, вероятно, один:

public static int bitLength(int i) {
    int len = 0;

    while (i != 0) {
        len += (i & 1);
        i >>>= 1;
    }

    return len;

}

Answer 10

int CountBits(uint value)
{
    for (byte i = 32; i > 0; i--)
    {
        var b = (uint)1 << (i - 1);
        if ((value & b) == b)
            return i;
    }
    return 0;
}