Ricerca di N bit contigui in un numero intero a sinistra della posizione MSB di un altro intero

Question

Il problema è: dato un numero intero val1 trovare la posizione del bit più alto impostato (Most Significant Bit) quindi, dato un secondo intero val2 trovare una regione contigua di bit non impostati a sinistra della posizione ottenuta dal primo intero. width specifica il numero minimo di bit non impostati che devono essere trovati in contiguità (ovvero width zeri senza quelli all'interno di essi).

Ecco il codice C per la mia soluzione:

#include <limits.h> /* for CHAR_BIT - number of bits in a char */ 

typedef unsigned int t; 
unsigned const t_bits = sizeof(t) * CHAR_BIT; 

_Bool test_fit_within_left_of_msb( unsigned width, 
            t val1, /* integer to find MSB of */ 
            t val2, /* integer to find width zero bits in */ 
            unsigned* offset_result) 
{ 
    unsigned offbit = 0; /* 0 starts at high bit */ 
    unsigned msb = 0; 
    t mask; 
    t b; 

    while(val1 >>= 1) /* find MSB! */ 
     ++msb; 

    while(offbit + width < t_bits - msb) 
    { 
     /* mask width bits starting at offbit */ 
     mask = (((t)1 << width) - 1) << (t_bits - width - offbit); 
     b = val2 & mask; 

     if (!b) /* result! no bits set, we can use this */ 
     { 
      *offset_result = offbit; 
      return true; 
     } 

     if (offbit++) /* this conditional bothers me! */ 
      b <<= offbit - 1; 

     while(b <<= 1) 
      offbit++; /* increment offbit past all bits set */ 
    } 
    return false; /* no region of width zero bits found, bummer. */ 
} 

Oltre a metodi più veloci di trovare il MSB del primo intero, il test ha commentato per uno zero offbit sembra un po 'estranea, ma necessario per saltare la il bit più alto di tipo t se è impostato. Spostando incondizionatamente lo spostamento b per offbit - 1 bit si otterrà un loop infinito e la maschera non supererà mai l'1 nel bit più alto di val2 (altrimenti, se il bit più alto è zero, nessun problema).

Ho anche implementato algoritmi simili ma lavorando a destra dell'MSB del primo numero, quindi non richiedono questa condizione apparentemente extra.

Come posso eliminare questa condizione aggiuntiva o, addirittura, esistono soluzioni molto più ottimali?

Modifica: alcuni sfondi non strettamente necessari. Il risultato dell'offset è un conteggio dei bit dal bit più alto, non dal bit basso come forse previsto. Questo farà parte di un algoritmo più ampio che analizza un array 2D per un'area 2D di zero bit. Qui, per il test, l'algoritmo è stato semplificato. val1 rappresenta il primo numero intero che non ha tutti i bit impostati trovati in una riga dell'array 2D. Da ciò la versione 2D eseguirà la scansione verso il basso, che rappresenta ciò che rappresenta val2.

Ecco un output mostra successo e fallimento:

t_bits:32 
    t_high: 10000000000000000000000000000000 (2147483648) 
--------- 

----------------------------------- 
*** fit within left of msb test *** 
----------------------------------- 
     val1: 00000000000000000000000010000000 (128) 
     val2: 01000001000100000000100100001001 (1091569929) 
msb: 7 
offbit:0 + width: 8 = 8 
     mask: 11111111000000000000000000000000 (4278190080) 
     b:  01000001000000000000000000000000 (1090519040) 
offbit:8 + width: 8 = 16 
     mask: 00000000111111110000000000000000 (16711680) 
     b:  00000000000100000000000000000000 (1048576) 
offbit:12 + width: 8 = 20 
     mask: 00000000000011111111000000000000 (1044480) 
     b:  00000000000000000000000000000000 (0) 
offbit:12 
iters:10 


***** found room for width:8 at offset: 12 ***** 

----------------------------------- 
*** fit within left of msb test *** 
----------------------------------- 
     val1: 00000000000000000000000001000000 (64) 
     val2: 00010000000000001000010001000001 (268469313) 
msb: 6 
offbit:0 + width: 13 = 13 
     mask: 11111111111110000000000000000000 (4294443008) 
     b:  00010000000000000000000000000000 (268435456) 
offbit:4 + width: 13 = 17 
     mask: 00001111111111111000000000000000 (268402688) 
     b:  00000000000000001000000000000000 (32768) 
***** mask: 00001111111111111000000000000000 (268402688) 
offbit:17 
iters:15 


***** no room found for width:13 ***** 

(iter è il conteggio di iterazioni del ciclo while interno, b è risultato val2 & mask)

Answer 1

Dopo aver implementato la mia risposta precedente ma lavorare per il diritto di MSB, ho visto che a parte una differenza molto piccola, le versioni sinistra e destra erano esattamente le stesse. Ciò ha portato alla realizzazione che non vi è alcun requisito reale per l'algoritmo di lavorare con un MSB da qualche valore precedente.

Quindi anche se questa risposta non soddisfa le specifiche della domanda, è la risposta corretta perché la specifica non era corretta.

metodo

#include<stdint.h> 

/* returns bit position within a 32bit integer, where 
    a region of contiguous zero bits can be found whose 
    count is equal to or greater than width. it returns 
    -1 on failure. 
*/ 

int binary_width_fit(unsigned width, uint32_t val) 
{ 
    int offset = 32; 
    uint32_t mask; 
    uint32_t b; 

    while(offset >= width) 
    { 
     mask = (((uint32_t)1 << width) - 1) << (offset - width); 
     b = val & mask; 
     if (!b) 
      return offset; 
     offset = __builtin_ctz(b); /* GCC builtin to Count Trailing Zeros */ 
    } 
    return -1; 
} 

Answer 2

Questa http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious ha diversi modi per calcola il numero intero senza segno log base 2 di un numero intero senza segno (che è anche la posizione del bit più alto impostato).

Penso che questo faccia parte di ciò che desideri. Sospetto che se sapessi davvero quello che vuoi, potrei suggerire un modo migliore di calcolarlo o qualcosa che abbia avuto lo stesso scopo.

Answer 3

count_leading_zero_bits è spesso una singola istruzione che il compilatore fornirà una funzione inline per. altrimenti mettilo in un loop.

count_trailing_zero_bits può utilizzare count_leading_zero_bits (x & -x) o una ricerca debruijn se il primo è un ciclo.

per semplicità presumo valori a 32 bit.

int offset_of_zero_bits_over_msb_of_other_value(unsigned width , unsigned value , unsigned other) { 
    int count = 0; 
    int offset = -1; 
    int last = 1; 
    int lz = count_leading_zero_bits(other); 
    other |= ((1<<(32-lz2))-1); // set all bits below msb 
    if (value & ~other) { 
    value |= other; // set all bits below msb of other 
    value = ~value; // invert so zeros are ones 
    while (value && count < width) { 
     count += 1; // the widest run of zeros 
     last = value; // for counting trailing zeros 
     value &= value >> 1; // clear leading ones from groups 
    } 
    offset = count_trailing_zero_bits(last); 
    } else { 
    count = lz2; 
    offset = 32 - lz2; 
    } 
    return (count < width) ? -1 : offset; 
} 

L'idea alla base del codice è questo:

val1: 00000000000000000000000010000000 (128) 
    val2: 01000001000100000000100100001001 (1091569929) 
    lz1: 24 
    lz2: 1 
    val2: 01000001000100000000100011111111 // |= ((1<<(32-lz1))-1); 
    val2: 10111110111011111111011100000000 // = ~val2 
    val2: 00011110011001111111001100000000 // &= val2>>1 , count = 1 
    val2: 00001110001000111111000100000000 // &= val2>>1 , count = 2 
    val2: 00000110000000011111000000000000 // &= val2>>1 , count = 3 
    val2: 00000010000000001111000000000000 // &= val2>>1 , count = 4 
    val2: 00000000000000000111000000000000 // &= val2>>1 , count = 5 
    val2: 00000000000000000011000000000000 // &= val2>>1 , count = 6 
    val2: 00000000000000000001000000000000 // &= val2>>1 , count = 7 
    val2: 00000000000000000000000000000000 // &= val2>>1 , count = 8 

Così ad ogni passo, tutte le gamme di zeri, ora quelli, sono rimpicciolita da destra. Quando il valore è zero, il numero di passi effettuati è la larghezza della corsa più ampia. In qualsiasi momento, il conteggio del numero di zeri finali darà l'offset all'intervallo più vicino di almeno count zeri.

Se in qualsiasi momento il conteggio supera la larghezza, è possibile interrompere l'iterazione. Il numero massimo di iterazioni è quindi la larghezza, non la dimensione della parola. Potresti fare questo O (log n) di larghezza, perché puoi raddoppiare la quantità di spostamento a ogni iterazione finché non superi la larghezza.

Ecco una ricerca DeBruijn per il conteggio dei bit zero finali per i valori a 32 bit.

static const int MultiplyDeBruijnBitPosition[32] = { 
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
}; 
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27]; 

Ho notato che in entrambi gli esempi, val1 aveva solo un singolo bit impostato. Se questo è il caso, puoi usare il trucco DeBruijn per trovare l'MSB.

Answer 4

Ecco il mio nuovo e migliorato algoritmo:

int test_fit_within_left_of_msb( unsigned width, 
            unsigned val1, 
            unsigned val2) 
{ 
    int offset = 32; 
    int msb = 0; 
    unsigned mask; 
    unsigned b; 

    msb = 32 - __builtin_clz(val1); /* GCC builtin to count Leading Zeros */ 

    while(offset - width > msb) 
    { 
     mask = (((unsigned)1 << width) - 1) << (offset - width); 
     b = val2 & mask; 

     if (!b) 
      return 32 - offset; 

     offset = __builtin_ctz(b); /* GCC builtin to Count Trailing Zeros */ 
    } 

    return -1; 
} 

Questo codice ha un sacco di miglioramenti sopra la mia implementazione iniziale. In primo luogo, la rimozione del ciclo interno while semplicemente contando i bit zero finali. In secondo luogo, ho anche fatto funzionare l'algoritmo con un offset che utilizza i valori di posizione di bit naturali e quindi rimosso alcune delle operazioni di addizione e sottrazione utilizzate dall'originale, fino alla dichiarazione di ritorno corretta. Potresti scegliere di sottrarre l'offset da 32.

Il punto importante qui nel codice, è l'algoritmo - mi rendo conto che ci sono preoccupazioni sulla portabilità e ipotesi fatte su tipi e dimensioni. Guardando indietro la pagina sull'output dove si trova la larghezza 8 nella posizione 12 eseguita in 10 iterazioni, il nuovo alogirmo fa lo stesso in 2 iterazioni del ciclo.

Ho usato i comandi incorporati GCC per comodità qui, il codice MultiplyDeBruijnBitPosition che drawonward fornito (da: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup) può essere utilizzato per sostituire __builtin_ctz, mentre __bultin_clz potrebbe essere sostituito con uno dei il logaritmo in base intero 2 codici della stessa pagina.

Una preoccupazione qui, però, sono i dati (con punte scarsamente set) che ho usato per testare questo con rende questo algoritmo rendimento migliore, questo sarà forse non sarà così grande guardando interi con punte più densamente set . (Non corretto: contando gli zeri finali evita questo caso negativo).

Answer 5

1 (veloce) è quello di utilizzare tabelle di ricerca (LUT) precalcolate per ogni byte 8bit:

PosOfFirst1, PosOfLast1, PosOfFirst0, PosOfLast0 - tutti gli array di 256 byte

precalculate la tabelle utilizzando: (soz per il povero, pseudocodice pascalish)

PosOfLast1:

FOR EACH ByteVal (0..255): 

if byteVal>127 return 8 
elseif byteVal>63 return 7 
... 
elseif byteVal>0 return 1 
else return 0 

PosOfFirst1: 

c:=0; 
while c<8 do 
begin 
bv = byteVal and 1; 
if bv=1 then return c 
else byteval shr 1;  
inc (c); 
end; 

Io uso semplici proc assemblatori per questi alg. PosOfFirst0 e PosOfLast0 Le LUT possono essere precalcolate utilizzando anche queste 2 tabelle - così come TRAILING & LEADING 0 (o 1) count. È utile anche pre-calcare le versioni "meno 1" di queste tabelle ....

È quindi possibile utilizzare (per byte 8 bit) var InputByte: Byte; FirstBit: = PosOfFirst1 [InputByte] // v.fast

Per le taglie più grandi (0, 16, 24, 32 +++++) utilizzare proc e loop che controllano ogni byte di 8 bit costituente. Potrebbe essere necessario l'accesso alla memoria della LUT ma questo metodo è ancora più veloce:

a) Può essere utilizzato facilmente senza richiedere una chiamata di procedura. b) scansione di un numero a 32 bit richiede 1 turno & confronto a 0 per byte con 1 ricerca necessaria (se viene trovato un byte diverso da zero) invece di n (0..32) turni, ands e confronti ... c) se programmato bene si fermerà dopo aver trovato 1 °/ultimo 1

Il principio LUT si applica al "conteggio della popolazione" + altro bit manip. routine ...

Cheers, PrivateSi

più veloce è meglio ?!