I need to test whether the positions (from 0 to 31 for a 32bit integer) with bit value 1 form a contiguous region. For example:
00111111000000000000000000000000 is contiguous
00111111000000000000000011000000 is not contiguous
I want this test, i.e. some function has_contiguous_one_bits(int)
, to be portable.
One obvious way is to loop over positions to find the first set bit, then the first non-set bit and check for any more set bits.
I wonder whether there exists a faster way? If there are fast methods to find the highest and lowest set bits (but from this question it appears there aren't any portable ones), then a possible implementation is
bool has_contiguous_one_bits(int val)
{
auto h = highest_set_bit(val);
auto l = lowest_set_bit(val);
return val == (((1 << (h-l+1))-1)<<l);
}
Just for fun, here are the first 100 integers with contiguous bits:
0 1 2 3 4 6 7 8 12 14 15 16 24 28 30 31 32 48 56 60 62 63 64 96 112 120 124 126 127 128 192 224 240 248 252 254 255 256 384 448 480 496 504 508 510 511 512 768 896 960 992 1008 1016 1020 1022 1023 1024 1536 1792 1920 1984 2016 2032 2040 2044 2046 2047 2048 3072 3584 3840 3968 4032 4064 4080 4088 4092 4094 4095 4096 6144 7168 7680 7936 8064 8128 8160 8176 8184 8188 8190 8191 8192 12288 14336 15360 15872 16128 16256 16320
they are (of course) of the form (1<<m)*(1<<n-1)
with non-negative m
and n
.
0x0
is compact. It's easier to define the opposite (not compact): if there are wo set bits such there is at least one unset bit between them.h>=l
by the (implied) functionality ofhighest_set_bit()
andlowest_set_bit()