2

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.

7 Answers 7

3

This should do what you want.

if(i == 0)
    return false;
while(i % 2 == 0) {
    i = i / 2;
}
return (i & (i + 1)) == 0;
2
  • 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. Jan 20, 2009 at 19:16
  • Good one! Much nicer than my solution. Jan 20, 2009 at 19:43
3
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
0
2

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)));
}
1

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 );
2
  • 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). Jan 20, 2009 at 19:39
  • (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!) Jan 20, 2009 at 19:40
1

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.

2
  • Argh, that beats mine by eliminating the count trailing zeroes! Although you'll want to make lowest_bit = a & -a; MSN
    – MSN
    Jan 20, 2009 at 20:44
  • Does it work? a&(a-1) removes the lowest bit, to isolate it you need a&(-a), or for unsigned a&(~a+1). But it's simpler, a|(a-1) set all trailing bits to 1. You then just check if this quantity +1 is a power of two, see my solution.
    – aka.nice
    Aug 18, 2012 at 22:08
1

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

0

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

You may use a lookup table.

3
  • 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). Jan 20, 2009 at 19:12
  • Binary search and hash tables will probably cost more than considering the number itself, both due to memory access. Jan 20, 2009 at 19:20
  • 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). Jan 20, 2009 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.