1

I need to write a function to check that some value is consecutive, for example 0b0011100, 0b001111111 or 0b100000000 are OK (return not 0) but 0b00110010 and 0b001010 are not (all the ones should be sequential).

But here is the catch I need to do it without any loop.

I'm using some crazy API which not allowed to use loop, I only have the following arithmetic function:

+, -, *, |, ||, &, &&, ~, !, TZC, POPCNT, <<, >>

Which are:

plus, minus, mult, bitwise or, logical or, bitwise and, logical and, bitwise not, logical not, trailing zero counter (count the zeros from the LSB to first 1), pop-counter (count the number of ones), shift-left and shift-right.

All values are 64 bit length.

pio
  • 500
  • 5
  • 12
  • What "crazy API" is this? At first glance this looks like homework. – MrSmith42 Mar 13 '17 at 16:50
  • 1
    What have you tried so far? Share your thoughts with us. – MrSmith42 Mar 13 '17 at 16:51
  • 1
    I'm voting to close this question as off-topic because it shows no sign of effort to solve it by the asker. – MrSmith42 Mar 13 '17 at 16:53
  • Have you read numerous pages about bit twiddling, bit hacks, bit tricks? – MBo Mar 13 '17 at 18:00
  • How many bits will there be? Your examples range from 6 to 9. If the number is small enough, you can start with a loop and then unroll the loop manually. – Adrian McCarthy Mar 13 '17 at 18:58
  • 3
    If you arent allowed to use Looping, try recursion – Thomas Mar 13 '17 at 19:24
  • sorry for the late respond: @MrSmith42 1. it's not an homework, it's just a parser of some documentation - some nasty and ugly thing, to change the source to support loop will be much more headache. 2. I read some algorithms [here](http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious) but didn't come with good solution. 3. my solution is ugly: find MSB [like this](http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i) find lsb with TZC and then (msb-lsb)==popcnt but as i said msb is ugly... – pio Mar 14 '17 at 18:16
  • @AdrianMcCarthy there are 64 bits, but it too ugly to write them all in binary format... – pio Mar 14 '17 at 18:17

1 Answers1

1
!(n >> (POPCNT(n) + TZC(n)))

If you count the number of ones and trailing zeros and shift by that amount then the result is only 0 if the ones are consecutive (because only then all set bits are erased by the shift).

a >> b is the same as a / 2^b or a / (1 << b).

Without shift:

!(POPCNT(n + 0b1) - 1) || !(POPCNT(n + 0b10) - 1) || !(POPCNT(n + 0b100) - 1) || ...
maraca
  • 8,468
  • 3
  • 23
  • 45
  • That operation `>>`, right shift, together with your similar operations `^` exponentiation and `<<` left shift, are not in the list of allowed operations. – Rory Daulton Mar 13 '17 at 23:42
  • 1
    I think it has to be there or the solution will be ugly. E.g. instead of shifting right by 3 you could do `& 0xFFFFFFFFFFFFFFF8` and drop the `!`. If there is an `if` you can do that 64 times. – maraca Mar 13 '17 at 23:51
  • 1
    I'm sorry SHL is actually supported. I edited the question... @maraca thx a lot!! – pio Mar 14 '17 at 18:19