Numero del bit non impostato rimasto del bit più significativo impostato?

Question

Supponendo che il numero intero a 64 bit 0x000000000000FFFF che sarebbe rappresentato come

00000000 00000000 00000000 00000000 
00000000 00000000 >11111111 11111111 

Come faccio a trovare la quantità di bit unset alla sinistra del bit più significativo impostato (quello contrassegnato con>)?

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

Dove count_bits_set è la versione più veloce di bit di conteggio si possono trovare. Vedere https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel per varie tecniche di conteggio dei bit.

Answer 2

Non sono sicuro di aver capito correttamente il problema. Penso che tu abbia un valore a 64 bit e vuoi trovare il numero di zeri iniziali in esso.

Un modo sarebbe quello di trovare il bit più significativo e semplicemente sottrarre la sua posizione da 63 (assumendo il bit più basso è il bit 0). Puoi scoprire il bit più significativo testando se un bit è impostato da un loop su tutti i 64 bit.

Un altro modo potrebbe essere utilizzare il (non standard) __builtin_clz in gcc.

Answer 3

stessa idea user470379's, ma il conto alla rovescia ...
Assumere tutti i 64 bit sono disinserita. Mentre il valore è maggiore di 0 mastio spostando il diritto valore e il numero di bit unset decremento:

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

Answer 4

Se avete a che fare con i numeri interi senza segno, si potrebbe fare questo:

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

non so in che modo si confronteranno le prestazioni con il ciclo ei metodi di conteggio che sono già stati offerti perché log2() potrebbe essere costoso.

Edit:

questo potrebbe causare alcuni problemi con interi ad alto valore dal momento che la funzione log2() è colata a double e può sorgere alcuni problemi numerici. È possibile utilizzare la funzione log2l() che funziona con long double. Una soluzione migliore sarebbe utilizzare una funzione intera log2() come in this question.

Answer 5

Prova

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

In rettilineo C (long long sono a 64 bit sulla mia configurazione), tratto da implementazioni Java simili: (aggiornato dopo un po 'di più la lettura del peso di Hamming)

Un po' di più spiegazione: la parte superiore imposta tutto il bit a destra del più significativo 1, quindi lo nega. (cioè tutti gli 0 a "sinistra" del più significativo 1 ora sono 1 e tutto il resto è 0).

Quindi ho utilizzato un'implementazione Hamming Weight per contare i bit.

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

Sarei curioso di vedere come questa fosse l'efficienza saggia. Lo ha provato con diversi valori e sembra funzionare.

Answer 7

Sono d'accordo con l'idea di ricerca binaria. Tuttavia due punti sono importanti qui:

1. La gamma di risposte valide alla tua domanda è 0-64 inclusiva.In altre parole, potrebbero esserci risposte diverse alla domanda. Penso che (quasi sicuramente) tutti coloro che hanno pubblicato la soluzione "binary search" abbiano perso questo punto, quindi avranno una risposta errata per zero o un numero con il bit MSB attivo.
2. Se la velocità è critica, è possibile evitare il ciclo. C'è un modo elegante per ottenere questo usando i modelli.

Il seguente roba modello trova il MSB correttamente di qualsiasi variabile di tipo 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

Qui si va, piuttosto banale per aggiornare di cui hai bisogno per altre dimensioni ...

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

Sulla base: 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;} 

Se vuoi una versione che ti permette di tenere il pranzo giù, ecco qui:

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

Come vedrai, puoi salvare i cicli su questo facendo un'attenta analisi dell'assemblatore, ma la strategia qui non è terribile. Il ciclo while opererà Lg [64] = 6 volte; ogni volta convertirà il problema in uno di contare il numero di bit iniziali su un numero intero di metà della dimensione. L'istruzione if all'interno del ciclo while pone la domanda: "posso rappresentare questo numero intero a metà di molti bit" o, analogamente, "se lo taglio a metà, l'ho perso?". Una volta completato il payload if(), il nostro numero sarà sempre nel numero più basso di bit. Nella fase finale, v è 0 o 1 e questo completa correttamente il calcolo.

Answer 10

Usa logaritmo in base 2 per ottenere la cifra più significativa che è 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 

e così via ... I numeri tra frazioni diventano del risultato di log. Quindi digitare il valore su un valore int per ottenere la cifra più significativa.

Una volta ottenuto questo numero, ad esempio b, il semplice 64-n sarà la risposta.

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

last_zero = 64 - get_pos_msd(n)