how to check consecutive value without using any loop

Question

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.

Answer 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) || ...