Минимальное количество бит для представления данного `int`?

Question

Минимальное количество бит для представления данного `int`?

В C ++, какой самый быстрый способ узнать, сколько бит необходимо для хранения данного int?

Я могу попытаться разделить число на 2 много раз, но деление происходит довольно медленно. Есть ли быстрый способ?

редактировать: Большое спасибо за ответы, ребята. Когда я говорю int в своем посте, я имею в виду любые 4 байта int. Например, если я храню 30665, я хочу получить в результате 15 бит.

3

algorithm bit-manipulation c++logarithm

Решение

Другие решения

Вы не можете выполнить это с алгоритмом, который «быстрее», чем смещение.

Но вы можете использовать следующий алгоритм (в том числе <cmath>):

int bits_n(int x) {
return (x != 0)
? std::ceil(std::log(x) / std::log(2))
: 1;
}

что, вероятно, достаточно быстро для большинства приложений.

std::log(x) / std::log(2) требуется выполнить логарифм в базе 2 (потому что стандартная библиотека C и C ++ не имеет функции выполнить это).

А также Вот Вы можете найти живой пример.

2

Для ненулевых неподписанный целочисленные типы, вы можете использовать для gcc / clang один из следующих

sizeof(unsigned)           - __builtin_clz(x)
sizeof(unsigned long)      - __builtin_clzl(x)
sizeof(unsigned long long) - __builtin_clzll(x)

Для и для 32-разрядных и 64-разрядных целых чисел в MSVC ++ вы можете определить переменную index сохранить результат

_BitScanReverse(&index, x)
_BitScanReverse64(&index, x)

Эти компиляторы будет делегировать инструкции по оборудованию, если ваш компьютер поддерживает его, или какой-то оптимизированный алгоритм бит-тиддлинга в противном случае. Вы можете написать свою собственную полуплатформенную независимую обертку вокруг нее, используя некоторые #ifdefs.

Есть связанный stdcxx-bitops GitHub репо Мэтью Фиораванте, который был плыл к std-proposals список рассылки в качестве предварительного предложения о добавлении constexpr библиотека побитовых операций для C ++. Если и когда это будет стандартизировано, будет что-то вроде std::clz() шаблон функции, который делает то, что вы ищете.

2

Посмотрите на знаменитый Бит Тиддлинг Хаки страница, если конкретный раздел на считая биты.

Для справки, вот способ Брайана Кернигана посчитать количество установленных бит:

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}

2

Давайте перефразируем вопрос (для целых чисел без знака в любом случае): упал ли msb моего целого числа?

(просто убедившись, что ты знаешь почему)

Давайте подумаем об этом в десятичном виде на секунду. Сколько цифр вам нужно, чтобы сохранить номер? Если у меня есть записанное число (как компьютер для любого числа), все, что мне нужно сделать, это подсчитать цифры и сообщить о позиции самой большой цифры.

Теперь люди не думают в двоичном формате, поэтому вы должны переводить между вашей десятичной цифрой и вашей двоичной цифрой … за исключением того, что компьютер сделает это за вас при разборе. Ввод вашей функции будет двоичным числом, поэтому все, что вам нужно сделать, это найти местоположение MSB.

Самый быстрый способ получить целое число без знака целого числа (к сожалению) не является супер переносимым.

Какой самый быстрый / самый эффективный способ найти старший установленный бит (msb) в целом числе в C?

Входит во все способы найти MSB. Короче говоря, в то время как C ++ может не дать вам хук напрямую, большинство компиляторов имеют встроенную команду сборки. Так что это будет самый быстрый способ.

1

Скорее всего быстрый способ заключается в использовании предварительно заполненной справочной таблицы.

const size_t bitsMap [] =
{
0, // value 0 (0)
1, // value 1 (1)
2, // value 2 (10)
2, // value 3 (11)
3, // value 4 (100)
// ...
};

Вы также можете заполнить этот массив (или vector или аналогичные) вычисляя его при запуске, используя математические средства, такие как ceil(log2(n)),

Теперь у вас есть номер n который вы хотите знать, сколько бит будет необходимо представить. Вы просто индексируете массив, используя n — значение stored есть количество битов.

int main()
{
for (int i = 0; i < 256; ++i)
{
const size_t bits = bitsMap [i];
cout << "The number " << i << " would take " << bits << " to represent."}
}

Индексирование массива происходит немедленно. Я не понимаю, как ты справишься с этим быстрее.

0

int num = number;
int count_bit =0;
while (num) {
num = num>>1;
count++;
}
std::cout << num << " needs " << count << " bits" << std::endl;

0

Сначала инициализируйте бит = 0. Затем цикл до тех пор, пока квадрат бита не станет равным числу.

    void bits(int x)
{
int bit = 1;

while(pow(2,bit) < x)
{
bit++;
}
printf("%d",bit);
}

Другой метод:

 int bit = static_cast<int>(log2(x));

0

Источник

Accepted Answer

Вы можете постепенно разбить значение пополам, чтобы сузить его быстрее.

int bits_needed(uint32_t value)
{
int bits = 0;
if (value >= 0x10000)
{
bits += 16;
value >>= 16;
}
if (value >= 0x100)
{
bits += 8;
value >>= 8;
}
if (value >= 0x10)
{
bits += 4;
value >>= 4;
}
if (value >= 0x4)
{
bits += 2;
value >>= 2;
}
if (value >= 0x2)
{
bits += 1;
value >>= 1;
}
return bits + value;
}

Посмотрите это в действии: http://ideone.com/1iH7hG

Редактировать: Извините, оригинальной версии требовался еще один термин. Это сейчас исправлено.

Изменить 2: В форме цикла, как предлагается в комментариях.

int bits_needed(uint32_t value)
{
int bits = 0;
for (int bit_test = 16; bit_test > 0; bit_test >>= 1)
{
if (value >> bit_test != 0)
{
bits += bit_test;
value >>= bit_test;
}
}
return bits + value;
}

Этот алгоритм возвращает 0 для ввода 0Это означает, что вам не нужны никакие биты для кодирования значения 0, Если вы предпочитаете это вернуть 1 вместо этого просто измените возвращаемое значение на bits + 1,

3