Количество неустановленных битов слева от старшего значащего установленного бита?

Question

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

00000000 00000000  00000000 00000000
00000000 00000000 >11111111 11111111

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

Answer 1

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

Немного больше объяснения: верхняя часть просто устанавливаетвсе бит справа от самого значимого 1, а затем отрицает его.(то есть все 0 слева от наиболее значимого 1 теперь равны 1, а все остальное равно 0).

Затем я использовал реализацию Вес Хэмминга для подсчета битов.

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 2

На основании: 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 3

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

#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 () может быть дорогим.

Редактировать

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

Answer 4

// 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 5

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

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 6

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

1. Диапазон правильных ответов на ваш вопрос от 0 до 64 включительно .Другими словами - могут быть 65 разных ответов на вопрос.Я думаю (почти наверняка) все, кто разместил решение «бинарного поиска», пропустили этот пункт, поэтому они получат неправильный ответ для нуля или числа с битом 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 7

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

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

Answer 8

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

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

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

Answer 9

Используйте основание журнала 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.

Answer 10

Попробуйте

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