how count number of 0 group bits in number? group bits consecutive 0 or 1 bits, example, 2 represented ....0000000000000000010 has 2 0 bits groups least significant bit , group starts after one. also, in bad need algorithms on bits manipulation if 1 has reference, please share
here couple fun ways it. #define-s @ beginning being able express function inputs in binary notation. 2 functions work variations on theme: first 1 uses de bruijn sequence , lookup table figure out how many trailing zeros there in parameter, , rest accordingly. second uses mod37 table same, similar in concept involves modulo operation instead of multiplication , bit shift. 1 of them faster. lazy figure out one.
this lot more code obvious solution. can effective if have zeros in input, requires 1 loop iteration (just 1 branch, actually) every 1-bit, instead of 1 loop iteration every bit.
#define hex__(n) 0x##n##lu #define b8__(x) ((x&0x0000000flu)? 1:0) \ +((x&0x000000f0lu)? 2:0) \ +((x&0x00000f00lu)? 4:0) \ +((x&0x0000f000lu)? 8:0) \ +((x&0x000f0000lu)? 16:0) \ +((x&0x00f00000lu)? 32:0) \ +((x&0x0f000000lu)? 64:0) \ +((x&0xf0000000lu)?128:0) #define b8(d) ((unsigned char)b8__(hex__(d))) #define b16(dmsb,dlsb) (((unsigned short)b8(dmsb)<<8) + b8(dlsb)) #define b32(dmsb,db2,db3,dlsb) (((unsigned long)b8(dmsb)<<24) \ + ((unsigned long)b8(db2)<<16) \ + ((unsigned long)b8(db3)<<8) \ + b8(dlsb)) unsigned int count_zero_groups_debruijn(unsigned int v) { // number of zero-bit groups (set 1 if high-bit zero) unsigned int g = (~(v & 0x80000000)) >> 31; // lookup table debruijn static const int _debruijntable[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 }; { // number of trailing zeros in v int tz = _debruijntable[((v & -v) * 0x077cb531u) >> 27]; // increment 0 group count if more 1 trailing 0 g += (tz > 0) * 1; // shift out trailing zeros , preceding 1 v = v >> (tz+1); } while (v); return g; } unsigned int count_zero_groups_mod37(unsigned int v) { // number of zero-bit groups (set 1 if high-bit zero) unsigned int g = (~(v & 0x80000000)) >> 31; // lookup table mod37 static const int _mod37table[] = { 0, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 }; { // number of trailing zeros in v int tz = _mod37table[(v & -v) % 37]; // increment 0 group count if more 1 trailing 0 g += (tz > 0) * 1; // shift out trailing zeros , preceding 1 v = v >> (tz+1); } while (v); return g; } int main(int argc, char* argv[]) { printf("zero groups: %d (should 6)\n", count_zero_groups_debruijn(b32(10011001,10000000,00001001,00010011))); printf("zero groups: %d (should 6)\n", count_zero_groups_debruijn(b32(10011001,10000000,00001001,00010000))); printf("zero groups: %d (should 6)\n", count_zero_groups_debruijn(b32(00011001,10000000,00001001,00010001))); printf("zero groups: %d (should 6)\n", count_zero_groups_debruijn(b32(00011001,10000000,00001001,00010000))); printf("zero groups: %d (should 0)\n", count_zero_groups_debruijn(b32(11111111,11111111,11111111,11111111))); printf("zero groups: %d (should 1)\n", count_zero_groups_debruijn(b32(00000000,00000000,00000000,00000000))); printf("zero groups: %d (should 6)\n", count_zero_groups_mod37 (b32(10011001,10000000,00001001,00010011))); printf("zero groups: %d (should 6)\n", count_zero_groups_mod37 (b32(10011001,10000000,00001001,00010000))); printf("zero groups: %d (should 6)\n", count_zero_groups_mod37 (b32(00011001,10000000,00001001,00010001))); printf("zero groups: %d (should 6)\n", count_zero_groups_mod37 (b32(00011001,10000000,00001001,00010000))); printf("zero groups: %d (should 0)\n", count_zero_groups_mod37 (b32(11111111,11111111,11111111,11111111))); printf("zero groups: %d (should 1)\n", count_zero_groups_mod37 (b32(00000000,00000000,00000000,00000000))); return 0; }
Comments
Post a Comment