Skip to content

Instantly share code, notes, and snippets.

@mah0x211

mah0x211/bittest.c

Last active August 4, 2017 15:17
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mah0x211/4571114 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mah0x211/4571114 to your computer and use it in GitHub Desktop.
Download ZIP
値が連続してるビットの数をカウントするのにもっとシンプルなやり方はないもんかなぁ。。＜ーあった。
Raw
bittest.c
/*
* bittest.c
* Copyright 2013 Masatoshi Teruya All rights reserved.
* twitter: @mah0x211
*/
#include <limits.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#define BIT4PAT "%d%d%d%d"
#define BIT8PAT BIT4PAT " " BIT4PAT
#define BIT12PAT BIT4PAT " " BIT8PAT
#define BIT16PAT BIT4PAT " " BIT12PAT
#define BIT20PAT BIT4PAT " " BIT16PAT
#define BIT24PAT BIT4PAT " " BIT20PAT
#define BIT28PAT BIT4PAT " " BIT24PAT
#define BIT32PAT BIT4PAT " " BIT28PAT
#define BIT36PAT BIT4PAT " " BIT32PAT
#define BIT64PAT BIT32PAT " " BIT32PAT
#define BIT4CHK(b) !!((b)&0x8), !!((b)&0x4), !!((b)&0x2), !!((b)&0x1)
#define BIT8CHK(b) BIT4CHK((b) >> 4), BIT4CHK(b)
#define BIT12CHK(b) BIT4CHK((b) >> 8), BIT8CHK(b)
#define BIT16CHK(b) BIT4CHK((b) >> 12), BIT12CHK(b)
#define BIT20CHK(b) BIT4CHK((b) >> 16), BIT16CHK(b)
#define BIT24CHK(b) BIT4CHK((b) >> 20), BIT20CHK(b)
#define BIT28CHK(b) BIT4CHK((b) >> 24), BIT24CHK(b)
#define BIT32CHK(b) BIT4CHK((b) >> 28), BIT28CHK(b)
#define BIT36CHK(b) BIT4CHK((b) >> 32), BIT32CHK(b)
#define BIT40CHK(b) BIT4CHK((b) >> 36), BIT36CHK(b)
#define BIT44CHK(b) BIT4CHK((b) >> 40), BIT40CHK(b)
#define BIT48CHK(b) BIT4CHK((b) >> 44), BIT44CHK(b)
#define BIT52CHK(b) BIT4CHK((b) >> 48), BIT48CHK(b)
#define BIT56CHK(b) BIT4CHK((b) >> 52), BIT52CHK(b)
#define BIT60CHK(b) BIT4CHK((b) >> 56), BIT56CHK(b)
#define BIT64CHK(b) BIT4CHK((b) >> 60), BIT60CHK(b)
#define bit_set(b,n) ((b) |= (n))
#define bit_unset(b,n) ((b) &= ~(n))
#define bit_sett(b,n,t) bit_set((b),(t)1<<(n))
#define bit_unsett(b,n,t) bit_unset((b),(t)1<<(n))
#define bit_test(l,r) ((l) & (r))
#define bit_cnt4(c)({ \
uint_fast64_t _n = ( ( (c) >> 1 ) & 0x5 ) + ( (c) & 0x5 ); \
( ( _n >> 2 ) & 0x3 ) + ( _n & 0x3 ); \
})
#define bit_cnt8(c) (bit_cnt4((c)>>4) + bit_cnt4(c))
#define bit_cnt16(c) (bit_cnt8((c)>>8) + bit_cnt8(c))
#define bit_cnt32(c) (bit_cnt16((c)>>16) + bit_cnt16(c))
#define bit_cnt64(c) (bit_cnt32((c)>>32) + bit_cnt32(c))
static inline uint_fast64_t _bit_cnt4( uint_fast64_t c ){
return bit_cnt4((uint_fast8_t)c);
}
static inline uint_fast64_t _bit_cnt8( uint_fast64_t c ){
return bit_cnt8((uint_fast8_t)c);
}
static inline uint_fast64_t _bit_cnt16( uint_fast64_t c ){
return bit_cnt16((uint_fast16_t)c);
}
static inline uint_fast64_t _bit_cnt32( uint_fast64_t c ){
return bit_cnt32((uint_fast64_t)c);
}
static inline uint_fast64_t _bit_cnt64( uint_fast64_t c ){
return bit_cnt64(c);
}
typedef uint_fast64_t(*_bit_cnt_t)( uint_fast64_t );
static const _bit_cnt_t _BIT_CNT[] = {
_bit_cnt4,
_bit_cnt8,
_bit_cnt16,
_bit_cnt32,
_bit_cnt64
};
#define bitvec_cnt(v,t,n) _bitvec_cnt(v,t,sizeof(t),sizeof(t)*CHAR_BIT,n)
#define _bitvec_cnt(v,t,s,b,n)({ \
uint_fast64_t _c = 0, _b = b, _n = (uint_fast64_t)n; \
if( n <= b ){ \
_c = _BIT_CNT[_b/CHAR_BIT]( ((t)*v >> (_b-_n)) ); \
} \
else { \
t *_p = (t*)v; \
uint_fast64_t _i = 0, \
_s = s, \
_m = _n % _b, \
_j = ( _n - _m )/_b, \
_l = _b/CHAR_BIT; \
for(; _i < _j; _i++ ){ \
_c += _BIT_CNT[_l](*_p); \
_p += _s; \
} \
_c += _BIT_CNT[_l]( ((t)*_p >> (_b-_m)) ); \
} \
_c; \
})
/*
* Bit Twiddling Hacks By Sean Eron Anderson
* Count the consecutive zero bits on the right with multiply and lookup
* http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
*/
/* m-sequence(maximal length sequence)
0x0218A7A392DD9ABFUL
0x02FCA8CF75A6C487UL
0x03F566ED27179461UL
0x03C953422DFAE33BUL
0x03848D96BBCC54FDUL
0x03731D7ED10B2A4FUL
*/
#define BIT_MLS 0x03F566ED27179461UL
/*
uint_fast8_t tbl[64] = {0};
uint_fast64_t m = BIT_MLS;
uint_fast8_t i = 0;
for(; i < 64; i++ ){
tbl[m >> 58] = i;
m <<= 1;
}
*/
static const uint_fast8_t BIT_MLS64TBL[64] = {
0, 1, 59, 2, 60, 40, 54, 3, 61, 32, 49, 41, 55, 19, 35, 4, 62, 52, 30, 33,
50, 12, 14, 42, 56, 16, 27, 20, 36, 23, 44, 5, 63, 58, 39, 53, 31, 48, 18,
34, 51, 29, 11, 13, 15, 26, 22, 43, 57, 38, 47, 17, 28, 10, 25, 21, 37, 46,
9, 24, 45, 8, 7, 6
};
/*
* Bit Twiddling Hacks By Sean Eron Anderson
* Reverse an N-bit quantity in parallel in 5 * lg(N) operations
* http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith32Bits
*/
#define bit_flip(b,t)({ \
uint_fast64_t _v = (b); \
uint_fast64_t _s = sizeof(t) * CHAR_BIT; \
uint_fast64_t _mask = ~0; \
while( (_s >>= 1) > 0){ \
_mask ^= (_mask << _s); \
_v = ((_v >> _s) & _mask) | ((_v << _s) & ~_mask); \
} \
_v; \
})
static void patbits( uint_fast64_t nbit )
{
uint_fast64_t bit = 0;
uint_fast64_t i;
printf( "print %llu bit pattern\n", nbit );
for( i = 0; i < nbit; i++ )
{
bit_sett( bit, i, uint_fast64_t );
if( i == 0 || !( i % 4 ) ){
printf( "-------------------------------------------------------------------------------| %02llu bit\n",
( ( ( i ) ? i / 4 : 0 ) + 1 ) << 2 );
}
printf( BIT64PAT "| i:%02llu, count:%02llu, val:%llu\n",
BIT64CHK(bit), i, bit_cnt64(bit), bit );
}
printf( "-------------------------------------------------------------------------------\n\n" );
}
static void patbits_utf8( const char *str )
{
char buf[5] = {0};
unsigned char c;
unsigned char *ptr = (unsigned char*)str;
uint_fast8_t len = 0;
printf( "print utf8 bit pattern for |%s|\n", str );
while( *ptr )
{
/*
左4ビット分のビットが立っている分がバイト数になる（仕様は4バイトまで）
0xxx xxxx ... = 1 byte(ascii)
110x xxxx ... = 2 bytes
1110 xxxx ... = 3 bytes
1111 xxxx ... = 4 bytes
この性質を利用してビット列を裏返す；
＃ループを使わないアルゴリズムを使えばループ無しでutf8文字のバイト数をカウントできる
xxxx xxx0 ... = 1 byte(ascii)
xxxx x011 ... = 2 bytes
xxxx 0111 ... = 3 bytes
xxxx 1111 ... = 4 bytes
裏返したビットを反転させる；
xxxx xxx1 ... = 1 byte(ascii)
xxxx x100 ... = 2 bytes
xxxx 1000 ... = 3 bytes
xxxx 0000 ... = 4 bytes
右から数えて一番最初にビットが立っている場所を探す；
xxxx xxx1 ... = 0 bit
xxxx x100 ... = 2 bit
xxxx 1000 ... = 3 bit
xxxx 0000 ... = 4 bit
*/
c = ~bit_flip( *ptr, unsigned char );
len = BIT_MLS64TBL[( ( c & ( ~c + 1 ) ) * BIT_MLS ) >> 58];
if( !len ){
len++;
}
else if( len > 4 ){
printf("invalid utf8 string: %c, %x", len, c );
exit(-1);
}
memcpy( (void*)buf, (void*)ptr, (size_t)len );
buf[len] = 0;
switch( len ){
case 1:
printf( "[%02x] len: %u |" BIT32PAT "| -> %s\n",
c, len,
BIT8CHK( *ptr ), BIT24CHK( 0x0 ),
buf );
break;
case 2:
printf( "[%02x] len: %u |" BIT32PAT "| -> %s -> %02x|%02x\n",
c, len,
BIT8CHK( *ptr ), BIT8CHK( ptr[1] ), BIT16CHK( 0x0 ),
buf, *ptr, ptr[1] );
ptr += 1;
break;
case 3:
printf( "[%02x] len: %u |" BIT32PAT "| -> %s -> %02x|%02x|%02x\n",
c, len,
BIT8CHK( *ptr ), BIT8CHK( ptr[1] ), BIT8CHK( ptr[2] ), BIT8CHK( 0x0 ),
buf, *ptr, ptr[1], ptr[2] );
ptr += 2;
break;
case 4:
printf( "[%02x] len: %u |" BIT32PAT "| -> %s -> %02x|%02x|%02x|%02x\n",
c, len,
BIT8CHK( *ptr ), BIT8CHK( ptr[1] ), BIT8CHK( ptr[2] ), BIT8CHK( ptr[3] ),
buf, *ptr, ptr[1], ptr[2], ptr[3] );
ptr += 3;
break;
}
ptr++;
}
}
static void test( void )
{
char *str = "abcdefg©ΩДアイウエオあいうえお𠀋𡈽𡌛𡑮𡢽𠮟𡚴𡸴𣇄𣗄𣜿𣝣𣳾𤟱𥒎𥔎𥝱𥧄𥶡𦫿𦹀𧃴𧚄𨉷𨏍𪆐𠂉𠂢𠂤𠆢𠈓𠌫𠎁𠍱𠏹𠑊𠔉𠗖𠘨𠝏𠠇𠠺𠢹𠥼𠦝𠫓𠬝𠵅𠷡𠺕𠹭𠹤𠽟𡈁𡉕𡉻𡉴𡋤𡋗𡋽𡌶𡍄𡏄𡑭𡗗𦰩𡙇𡜆𡝂𡧃𡱖𡴭𡵅𡵸𡵢𡶡𡶜𡶒𡶷𡷠𡸳𡼞𡽶𡿺𢅻𢌞𢎭𢛳𢡛𢢫𢦏𢪸𢭏𢭐𢭆𢰝𢮦𢰤𢷡𣇃𣇵𣆶𣍲𣏓𣏒𣏐𣏤𣏕𣏚𣏟𣑊𣑑𣑋𣑥𣓤𣕚𣖔𣘹𣙇𣘸𣘺𣜜𣜌𣝤𣟿𣟧𣠤𣠽𣪘𣱿𣴀𣵀𣷺𣷹𣷓𣽾𤂖𤄃𤇆𤇾𤎼𤘩𤚥𤢖𤩍𤭖𤭯𤰖𤴔𤸎𤸷𤹪𤺋𥁊𥁕𥄢𥆩𥇥𥇍𥈞𥉌𥐮𥓙𥖧𥞩𥞴𥧔𥫤𥫣𥫱𥮲𥱋𥱤𥸮𥹖𥹥𥹢𥻘𥻂𥻨𥼣𥽜𥿠𥿔𦀌𥿻𦀗𦁠𦃭𦉰𦊆𦍌𣴎𦐂𦙾𦚰𦜝𦣝𦣪𦥑𦥯𦧝𦨞𦩘𦪌𦪷𦱳𦳝𦹥𦾔𦿸𦿶𦿷𧄍𧄹𧏛𧏚𧏾𧐐𧑉𧘕𧘔𧘱𧚓𧜎𧜣𧝒𧦅𧪄𧮳𧮾𧯇𧲸𧶠𧸐𧾷𨂊𨂻𨊂𨋳𨐌𨑕𨕫𨗈𨗉𨛗𨛺𨥉𨥆𨥫𨦇𨦈𨦺𨦻𨨞𨨩𨩱𨩃𨪙𨫍𨫤𨫝𨯁𨯯𨴐𨵱𨷻𨸟𨸶𨺉𨻫𨼲𨿸𩊠𩊱𩒐𩗏𩙿𩛰𩜙𩝐𩣆𩩲𩷛𩸽𩸕𩺊𩹉𩻄𩻩𩻛𩿎𪀯𪀚𪃹𪂂𢈘𪎌𪐷𪗱𪘂𪘚𪚲";
patbits(64);
patbits_utf8( str );
}
static void test2(void)
{
uint_fast64_t hash = BIT_MLS;
uint_fast64_t b = 0xc;
uint_fast64_t x = b & ( ~b + 1 );
uint_fast64_t y = x * hash;
uint_fast64_t z = y >> 58;
printf(
BIT64PAT " -> %llu\n"
BIT64PAT " -> %llu\n"
BIT64PAT " -> %llu\n"
BIT64PAT " -> %llu\n"
BIT64PAT " -> %llu\n"
"bit at %u",
BIT64CHK( b ), b,
BIT64CHK( ~b ), ~b,
BIT64CHK( x ), x,
BIT64CHK( y ), y,
BIT64CHK( z ), z,
BIT_MLS64TBL[z]
);
}
int main( int argc, const char *argv[] )
{
test();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment