Non looping way to check if every Nth bit is set, with or without an offset?-CodePudding

For example, is every 4th bit set.

1000.1000 true
1010.1000 true
0010.1000 false

with offset of 1
0100.0100 true
0101.0100 true
0001.0100 false

Currently I am doing this by looping through every 4 bits

int num = 170; //1010.1010
int N = 4;
int offset = 0; //[0, N-1]
bool everyNth = true;
for (int i = 0; i < intervals ; i  ){
    if(((num >> (N*i)) & ((1 << (N - 1)) >> offset)) == 0){
        every4th = false;
        break;
    }
}
return everyNth;



EXPLANATION OF CODE:
num = 1010.1010

The loop makes it so I look at each 4 bits as a block by right shifting * 4. 
num >> 4 = 0000.1010

Then an & for a specific bit that can be offset.
And to only look at a specific bit of the chunk, a mask is created by ((1 << (N - 1)) >> offset)

0000.1010
     1000 (mask >> offset0)
  OR 0100 (mask >> offset1)
  OR 0010 (mask >> offset2)
  OR 0001 (mask >> offset3)

Is there a purely computational way to do this? Like how you can XOR your way through to figure out parity. I am working with 64 bit integers for my case, but I am wondering this in a more general case.

Additionally, I am under the assumption that bit operators are one of the fastest methods for calculations or math in general. If this is not true, please feel free to correct me on what the time and place is for bit operators.

CodePudding user response：

If we had a mask M in which every Nth bit is set, then testing whether every Nth bit in a given integer x is set could be calculated as (x & M) == M. Or with offset, you could use ((x << offset) & M) == M. Shifting M right is fine too.

If N is constant, that's all there is to it, just use the right M.

If N is variable, the question becomes, how do we get a mask in which every Nth bit is set.

Here is a simple way to do that:

Start by setting the Nth bit
"Double" the mask until done

For example,

ulong M = 1UL << (N - 1);
do
{
    M |= M << N;
    N  = N;
} while (N < 64);

That is clearly still a loop. But it's not a bit-by-bit loop, it makes only a logarithmic number of iterations.

You could precompute the masks and store them in a small array, the range of N is necessarily small.

There may also be a way based on ulong.MaxValue / ((1UL << N) - 1) but that needs something more to "align" the mask and 64-bit division is not so great anyway. Perhaps there is a smarter way to get the mask.

I am under the assumption that bit operators are one of the fastest methods for calculations or math in general

Bitwise operations are some of the fastest operations, but addition is equally fast, and multiplication is not that far behind (and a multiplication can do a lot more work at once, compared to how much more it costs).