Wie finden Sie das erste Bit, das in C anders ist?

Question

Ich möchte mit Integer in C vergleichen und das Problem besteht darin, das niedrigstwertige Bit zu finden, das anders ist. Was ist der schnellste Weg in C?

Beispiel:

   Bit 

       ---- 
a = 13 (binary 1101) 
b = 9 (binary 1001) 
       ^

Das Ergebnis hier sollte 2 sein, da das Bit 2 ist das erste Bit, das anders ist.

Answer 1

ffs() aus <strings.h> gibt die Position des ersten Bits gesetzt, wobei die Bits gezählt sind bei 1 für das niedrigstwertige Bit beginnend (und ffs(0) kehrt Null):

unsigned a = 0x0D; 
unsigned b = 0x09; 

unsigned x = a^b; 
int pos = ffs(x) - 1; 
if (pos == -1) { 
    // a and b are equal 
} else { 
    // pos is the position of the first difference 
} 

Answer 2

Bit Twiddling Hacks bietet eine ausgezeichnete Sammlung von, äh, Bit Twiddling Hacks, mit Performance/Optimierung Diskussion beigefügt. Für Ihr Problem (von dieser Seite) können Sie verwenden Multiplikations- und Lookup-Strategie:

unsigned int c = a^b; 
int r;   // result goes here 
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)((c & -c) * 0x077CB531U)) >> 27]; 

Referenzen:

• "Using de Bruijn Sequences to Index a 1 in a Computer Word" - Erklärung darüber, warum der obige Code funktioniert.

Answer 3

#include <stdint.h> 

int bit_count(uint32_t bits) { 
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); 
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); 
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); 
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); 
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff); 
} 

int func(unsigned a, unsigned b){ 
    unsigned x = a^b; 
    return x ? bit_count((x&(-x))-1) : -1; 
}