Liczba bitów nieuzbrojonych w lewo od najbardziej znaczącego set bit?

Question

Zakładając, że 64-bitowej liczby całkowitej 0x000000000000FFFF która byłaby oznaczona jako

00000000 00000000 00000000 00000000 
00000000 00000000 >11111111 11111111 

Jak znajdę ilość unset bitów w lewo z najbardziej znaczącym bitem (jedna oznaczona>)?

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

Gdzie count_bits_set jest najszybszą wersją zliczających bitów, które można znaleźć. Zobacz https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel dla różnych technik liczenia bitów.

Answer 2

Nie jestem pewien, czy poprawnie zrozumiałem problem. Myślę, że masz wartość 64-bitową i chcesz znaleźć w niej liczbę zer wiodących.

Jednym ze sposobów jest znalezienie najbardziej znaczącego bitu i po prostu odjęcie jego pozycji od 63 (zakładając, że najniższy bit jest bitem 0). Możesz dowiedzieć się najbardziej znaczący bit, sprawdzając, czy bit jest ustawiony z pętli na wszystkie 64 bity.

Innym sposobem może być użycie (niestandardowego) __builtin_clz w gcc.

Answer 3

sam pomysł jak user470379's, ale odliczanie ...
Załóżmy wszystkie 64 bity są rozbrojony. Podczas gdy wartość jest większa niż 0 cofanie prawo wartości i zmniejszanie liczby unset bitów:

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

Answer 4

Jeśli masz do czynienia z liczb całkowitych bez znaku, można to zrobić:

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

nie wiem jak porównać wydajność do pętli i policzyć metody, które już zostały zaoferowane, ponieważ log2() może być kosztowny.

Edit:

Może to powodować pewne problemy z wysokimi wartościami całkowitymi ponieważ funkcja log2() rzuca do double i pewne problemy numeryczne mogą się pojawić. Można użyć funkcji log2l(), która współpracuje z long double. Lepszym rozwiązaniem byłoby użycie funkcji integer log2(), jak w this question.

Answer 5

Spróbuj

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

W prostej C (long long są 64-bitowe na mojej konfiguracji), wykonane z podobnych wdrożeń Java: (zaktualizowane po trochę więcej czytania na Hamminga masy)

Trochę więcej wyjaśnienie: Górna część po prostu ustawia cały bit na prawo od najbardziej znaczącego 1, a następnie neguje go. (tzn. wszystkie liczby 0 do "lewej" najbardziej znaczącej wartości 1 wynoszą teraz 1, a wszystko inne 0).

Następnie użyłem implementacji Hamming Weight, aby policzyć bity.

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

Chciałbym zobaczyć, jak to było pod względem wydajności. Przetestowałem to z kilkoma wartościami i wydaje się, że działa.

Answer 7

Zgadzam się z pomysłem wyszukiwania binarnego. Jednak dwa punkty są ważne tutaj:

1. Zakres prawidłowych odpowiedzi na swoje pytanie wynosi od 0 do 64 włącznie.Innymi słowy - mogą istnieć różne odpowiedzi na pytanie: . Myślę (prawie na pewno), że wszyscy, którzy zamieścili rozwiązanie "szukania binarnego", przegapili ten punkt, dlatego otrzymają błędną odpowiedź na zero lub na liczbę z włączonym bitem MSB.
2. Jeśli prędkość jest krytyczna - możesz chcieć uniknąć pętli. Jest elegancki sposób na osiągnięcie tego przy użyciu szablonów.

Następująca treść szablonu prawidłowo odnajduje MSB dowolnej zmiennej typu niepodpisana.

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

Proszę, dość trywialny do aktualizacji, jak trzeba dla innych rozmiarów ...

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

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

Jeśli chcesz wersję, która pozwala ci zachować przerwę na lunch, proszę:

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

Jak widać, można zapisać cykle na tej podstawie dokładnej analizy asemblera, ale strategia tutaj nie jest straszna. Pętla while będzie działała Lg [64] = 6 razy; za każdym razem przekształci problem w jeden z liczenia liczby wiodących bitów na liczbie całkowitej o połowę mniejszej. Instrukcja if wewnątrz pętli while zadaje pytanie: "czy mogę reprezentować tę liczbę całkowitą w połowie tak dużej liczby bitów", lub analogicznie, "czy przecię to na pół, czy ją zgubiłem?". Po zakończeniu ładowania funkcji if() nasz numer będzie zawsze znajdował się w najniższych bitach n. W ostatnim etapie v ma wartość 0 lub 1, co powoduje prawidłowe wykonanie obliczeń.

Answer 10

logu podstawa 2, aby Ci najbardziej znacząca cyfra, która wynosi 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 

i tak dalej ... numery w pomiędzy stają frakcji wyniku dziennika. Tak więc typowanie wartości na wartość int daje najbardziej znaczącą cyfrę.

Po uzyskaniu tego numeru, powiedz b, proste 64 - n będzie odpowiedzią.

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

last_zero = 64 - get_pos_msd(n)