Число вставленных бит слева от наиболее значимого бита набора?

Question

Предполагая 64биное число 0x000000000000FFFF которое будет представлено как

00000000 00000000 00000000 00000000 
00000000 00000000 >11111111 11111111 

Как найти количество неустановленных бит слева от наиболее значимого набора бит (один отмечен>)?

Answer 1

// clear all bits except the lowest set bit 
x &= -x;  

// if x==0, add 0, otherwise add x - 1. 
// This sets all bits below the one set above to 1. 
x+= (-(x==0))&(x - 1); 

return 64 - count_bits_set(x); 

Где count_bits_set это самый быстрый вариант подсчета битов можно найти. См. https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel для различных методов подсчета бит.

Answer 2

Я не уверен, что правильно понял проблему. Я думаю, что у вас есть 64-битное значение и вы хотите найти количество ведущих нулей в нем.

Один из способов - найти самый старший бит и просто вычесть его позицию из 63 (при условии, что младший бит бит 0). Вы можете узнать самый старший бит, проверяя, установлен ли бит из цикла по всем 64 битам.

Другим способом может быть использование (нестандартного) __builtin_clz в gcc.

Answer 3

Та же самая идея, как user470379's, но обратный отсчет ...
Предположим, все 64 бита убираются. В то время как значение больше 0 Keep сдвигая правильное значение и декремента количество неустановленных битов:

/* untested */ 
int countunsetbits(uint64_t val) { 
    int x = 64; 
    while (val) { x--; val >>= 1; } 
    return x; 
} 

Answer 4

Если вы имеете дело с целыми числами без знака, вы можете сделать это:

#include <math.h> 
int numunset(uint64_t number) 
{ 
    int nbits = sizeof(uint64_t)*8; 
    if(number == 0) 
     return nbits; 
    int first_set = floor(log2(number)); 
    return nbits - first_set - 1; 
} 

Я не знаю, как он будет сравнивать производительность с методами цикла и подсчета, которые уже были предложены, поскольку log2() может быть дорогостоящим.

Edit:

Это может вызвать некоторые проблемы, связанные с высокими значениями целых чисел, так как функция log2() бросает в double и могут возникнуть некоторые численные вопросы. Вы можете использовать функцию log2l(), которая работает с long double. Лучшим решением было бы использовать целое число log2(), как в this question.

Answer 5

Попробуйте

int countBits(int value) 
{ 
    int result = sizeof(value) * CHAR_BITS; // should be 64 

    while(value != 0) 
    { 
     --result; 
     value = value >> 1; // Remove bottom bits until all 1 are gone. 
    } 
    return result; 
} 

Answer 6

В прямой C (долго долго 64 бит на моей установке), взяты из подобных реализаций Java: (обновляется после немного больше чтения на Хемминга весе)

Побольше Объяснение: Верхняя часть просто устанавливает все бит справа от наиболее значимого 1, а затем отменяет его. (т. е. все 0 в «левом» из наиболее значимых 1 теперь 1, а все остальное - 0).

Затем я использовал реализацию Hamming Weight для подсчета бит.

unsigned long long i = 0x0000000000000000LLU; 

i |= i >> 1; 
i |= i >> 2; 
i |= i >> 4; 
i |= i >> 8; 
i |= i >> 16; 
i |= i >> 32; 
// Highest bit in input and all lower bits are now set. Invert to set the bits to count. 
i=~i; 

i -= (i >> 1) & 0x5555555555555555LLU; // each 2 bits now contains a count 
i = (i & 0x3333333333333333LLU) + ((i >> 2) & 0x3333333333333333LLU); // each 4 bits now contains a count 
i = (i + (i >> 4)) & 0x0f0f0f0f0f0f0f0fLLU; // each 8 bits now contains a count 
i *= 0x0101010101010101LLU; // add each byte to all the bytes above it 
i >>= 56; // the number of bits 

printf("Leading 0's = %lld\n", i); 

Мне было бы интересно узнать, насколько это было эффективно. Протестировал его с несколькими значениями, хотя и, похоже, работает.

Answer 7

Я согласен с идеей бинарного поиска. Однако важны два момента здесь:

1. Диапазон действительных ответов на ваш вопрос от 0 до 64 включительно .Другими словами - может быть различные ответы на вопрос. Я думаю (почти наверняка) все, кто разместил решение «двоичного поиска», пропустили этот момент, поэтому они получат неправильный ответ для нуля или числа с битом MSB.
2. Если скорость критическая - вы можете избежать цикла. Существует элегантный способ добиться этого с помощью шаблонов.

Следующий шаблонный материал находит MSB правильно любой переменной unsigned.

// helper 
template <int bits, typename T> 
bool IsBitReached(T x) 
{ 
    const T cmp = T(1) << (bits ? (bits-1) : 0); 
    return (x >= cmp); 
} 

template <int bits, typename T> 
int FindMsbInternal(T x) 
{ 
    if (!bits) 
     return 0; 

    int ret; 
    if (IsBitReached<bits>(x)) 
    { 
     ret = bits; 
     x >>= bits; 
    } else 
     ret = 0; 

    return ret + FindMsbInternal<bits/2, T>(x); 
} 

// Main routine 
template <typename T> 
int FindMsb(T x) 
{ 
    const int bits = sizeof(T) * 8; 
    if (IsBitReached<bits>(x)) 
     return bits; 

    return FindMsbInternal<bits/2>(x); 
} 

Answer 8

Здесь вы идете, довольно тривиальной обновить, как вам нужно для других размеров ...

int bits_left(unsigned long long value) 
{ 
    static unsigned long long mask = 0x8000000000000000; 
    int c = 64; 
    // doh 
    if (value == 0) 
    return c; 

    // check byte by byte to see what has been set 
    if (value & 0xFF00000000000000) 
    c = 0; 
    else if (value & 0x00FF000000000000) 
    c = 8; 
    else if (value & 0x0000FF0000000000) 
    c = 16; 
    else if (value & 0x000000FF00000000) 
    c = 24; 
    else if (value & 0x00000000FF000000) 
    c = 32; 
    else if (value & 0x0000000000FF0000) 
    c = 40; 
    else if (value & 0x000000000000FF00) 
    c = 48; 
    else if (value & 0x00000000000000FF) 
    c = 56; 

    // skip 
    value <<= c; 

    while(!(value & mask)) 
    { 
    value <<= 1; 
    c++; 
    } 

    return c; 
} 

Answer 9

основы: http://www.hackersdelight.org/HDcode/nlz.c.txt

template<typename T> int clz(T v) {int n=sizeof(T)*8;int c=n;while (n){n>>=1;if (v>>n) c-=n,v>>=n;}return c-v;} 

Если вы хотите версию, вы можете оставить свой обед, здесь вы:

int clz(uint64_t v) { 
    int n=64,c=64; 
    while (n) { 
     n>>=1; 
     if (v>>n) c-=n,v>>=n; 
    } 
    return c-v; 
} 

Как вы увидите, вы можете сэкономить на этом циклы тщательным анализом ассемблера, но стратегия здесь не ужасная. Цикл while будет работать Lg [64] = 6 раз; каждый раз он преобразует проблему в один из подсчета числа ведущих бит на целое число в два раза. Оператор if внутри цикла while задает вопрос: «могу ли я представить это целое число в два раза меньше» или аналогично «если я разрежу это пополам, я потерял его?». После того, как полезная нагрузка if() будет завершена, наш номер всегда будет в младших n бит. На заключительном этапе v является либо 0, либо 1, и это завершает расчет правильно.

Answer 10

Использование журнала базы 2, чтобы получить Вас наиболее значительную цифру, которая 1.

log(2) = 1, meaning 0b10 -> 1 
log(4) = 2, 5-7 => 2.xx, or 0b100 -> 2 
log(8) = 3, 9-15 => 3.xx, 0b1000 -> 3 
log(16) = 4 you get the idea 

и так далее ... Числа в между фракциями стали результатом журнала. Таким образом, приведение значения к int дает вам самую значительную цифру.

Как только вы получите это число, скажем b, простой 64-n будет ответом.

function get_pos_msd(int n){ 
    return int(log2(n)) 
} 

last_zero = 64 - get_pos_msd(n)