Detecting single one-bit streams within an integer

Question

I have to check a number if it satisfies the following criteria:

• in binary, all one-bits must be successive.
• the number must have at least one bit set.
• the successive one-bits may start at the MSB or end at the LSB, so it's perfectly valid if the number is made up of a single one-bit stream followed by a zero-bit stream or vice versa.

I wrote a code that checks for these conditions for a real-world problem (checking data-file integrity).

It works without problems and it's anything but time-critical, but I'm an old bit-twiddeling freak and love such puzzles, so I've tried to came up with a more clever way to check for single-one-bit streams.

Cases where the string is surrounded by zeros is easy, but that one can't deal with the special cases.

Any ideas, binary hacks and partial solutions are welcome!

---

To make my requirements more clear some examples: The following numbers satisfy my criteria:

  0x80000000
  0x00000001
  0xff000000
  0x000000ff
  0xffffffff
  0x000ff000

The following numbers don't (as they have more than one successive string of ones):

  0xf00000f <- one-bit streams should not wrap-around at 2^n
  0x0001700 <- a trivial example.
  0x0000000 <- no one bit at all.

Answer 1

bool isOK(uint val) {
   while (val != 0 && (val & 1u) == 0) val >>= 1;
   if (val == 0) return false;
   while (val != 0 && (val & 1u) == 1) val >>= 1;
   return val == 0;
}

; x86 assembly
mov eax, THE_NUMBER ; store the number in eax
bsf ecx, eax
jz .notok
mov edi, 1
shl edi, cl
mov esi, eax
add esi, edi
test esi, eax
jnz .notok
mov eax, 1
jmp .end
.notok:
mov eax, 0
.end: ; eax = 1 if satisfies the criteria, otherwise it's 0

Answer 2

This should do what you want.

if(i == 0)
    return false;
while(i % 2 == 0) {
    i = i / 2;
}
return (i & (i + 1)) == 0;

Answer 3

I solved almost same problem there http://smallissimo.blogspot.fr/2012/04/meteor-contest-part-3-reducing.html in method hasInsetZero: (and used several other bit tricks)

hasInsetZero: aMask
    | allOnes |
    allOnes := aMask bitOr: aMask - 1.
    ^(allOnes bitAnd: allOnes + 1) > 0

It's Smalltalk code, but translated in C (we need the negation and care for 0), that would be:

int all_set_bits_are_consecutive( x )
/* return non zero if at least one bit is set, and all set bits are consecutives */
{
   int y = x | (x-1);
   return x && (! (y & (y+1)));
}

Answer 4

Assuming you want fast, the basic algorithm will be:

1. Find the lowest bit set.
2. Shift number by the index of lowest bit set.
3. Add 1.
4. If result is a power of two and non-zero, success!

All of these operations are either O(1) or O(log(integer bit width)), as follows:

unsigned int lowest_power_of_2(unsigned int value) 
{ return value & -value; }

unsigned int count_bits_set(unsigned int value) 
{ /* see counting bits set in parallel */ }

unsigned int lowest_bit_set_or_overflow_if_zero(unsigned int value)
{ return count_bits_set(lowest_power_of_2(value) - 1); }

unsigned int is_zero_or_power_of_2(unsigned int value)
{ return value && (value & (value - 1))==0; }

bool magic_function(unsigned in value)
{ return is_zero_or_power_of_2((value >> (lowest_bit_set_or_overflow_if_zero(lowest_power_of_2(value)))) + 1); }

Edit: updated final operation to account for zero, but the OP's algorithm is much faster since it's all constant operation (although accounting for overflow would be a PITA).

MSN

Answer 5

I would use bsr and bsf to determine the min and max bit set in the number. From that, create a valid number that satisfies the criteria. Compare the known valid number to the actual number for equality. No loops and only one compare.

pseudo-code:

min_bit = bsf(number);
max_bit = bsr(number);
valid_number = ~(-1 << (max_bit - min_bit) ) << min_bit;
return ( number == valid_number );

Answer 6

My work-in-progress version. Not ment as an answer, just to give some more ideas and to document my current approach:

int IsSingleBitStream (unsigned int a)
{
  // isolate lowest bit:
  unsigned int lowest_bit = a & (a-1);

  // add lowest bit to number. If our number is a single bit string, this will
  // result in an integer with only a single bit set because the addition will     
  // propagate up the the highest bit. We ought to end up with a power of two.
  a += lowest_bit;

  // check if result is a power of two:
  return (!a || !(a & (a - 1)));
}

This code will not work if the line:

a+= lowest_bit

overflows. Also I'm unsure if my "isolate single bit" code works if there is more than one bit-field.

Answer 7

There are (N^2 - N) / 2 possibilities for a N-bit integer (496 for 32-bit).

You may use a lookup table.