views:

273

answers:

6

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.
+2  A: 
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
Mehrdad Afshari
+1 for assembly hacking!
Nils Pipenbrinck
+2  A: 

This should do what you want.

if(i == 0)
    return false;
while(i % 2 == 0) {
    i = i / 2;
}
return (i & (i + 1)) == 0;
Glomek
This won't work for a number with every bit set :)
Mehrdad Afshari
Oops. It wouldn't have worked with anything. I meant bitwise and, not xor. And yes, it works for a number with every bit set. In that case, i+1 is zero, anded with anything is zero.
Glomek
Yeah, this works pretty well.
Mehrdad Afshari
Good one! Much nicer than my solution.
Nils Pipenbrinck
Very nice, optimal solution.
Ates Goral
A: 

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

You may use a lookup table.

Quassnoi
How would you search for the number in the table? It will probably be more costly than just considering the number (the number can be stored in a register which will not have the cost of memory access for the lookup table).
Mehrdad Afshari
Ever heard of binary search?
Quassnoi
Binary search and hash tables will probably cost more than considering the number itself, both due to memory access.
Mehrdad Afshari
Hm. nice idea. However, out of the blue I'd think that a 2K table will be slower in average than a brute force search (think cache-misses ect).
Nils Pipenbrinck
+1  A: 

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

MSN
+1  A: 

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 );
gatorfax
Good one! I'd use bsr and bsf as well on x86 (nice instruction but noone uses them...). However, I have an embedded background, and also most CPU's have one way or another to scan for a bit they only care about the highest bit (so BSR is expensive).
Nils Pipenbrinck
(cames from the tradition that low-power CPU's don't have a divide instruction btw. Something like Count Leading Zeroes as a one-cycle instruction accelerates software-divisions quite a bit!)
Nils Pipenbrinck
+1  A: 

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.

Nils Pipenbrinck
Argh, that beats mine by eliminating the count trailing zeroes!Although you'll want to make lowest_bit = a MSN
MSN