Find the nth set bit

Help
1

I don’t think this is possible but I will ask anyway.
In my program I loop through the bits of a u64 with:

pub fn bitloop(bitboard: *u64) ?u6 {
    if (bitboard.* == 0) return null;
    defer bitboard.* &= (bitboard.* - 1);
    return @intCast(@ctz(bitboard.*));
}

in a lot of routines.

Now I need a trick (for a crazy compression trick).
Is it actually possible to directly get the nth set bit?

for example for this reading from LSB-MSB from left to right for simplicity:

00001101 // our bits
01234567 // bitnumbers

I would like to get the bitindex for the second set bit, which should give 5.
or the bitindex for the third set bit which is 7.

without looping through the bits. Is that possible?

1 Like
2

This will be easy if pdep/pext gets merged

1 Like
3 
// Note: This requires x86-64 and the BMI2 instruction set.
pub fn getNthSetBit(bitboard: u64, n: u6) ?u6 {
    // Return null if we are asking for a bit that doesn't exist
    if (@popCount(bitboard) <= n) return null;
    
    const nth_bit = @as(u64, 1) << n;
    
    // PDEP (Parallel Bit Deposit) magic via inline assembly
    const isolated = asm (
        "pdep %[mask], %[val], %[out]"
        : [out] "=r" (-> u64),
        : [val] "r" (nth_bit),
          [mask] "r" (bitboard),
    );
    
    return @intCast(@ctz(isolated));
}

This uses the hardware PDEP instruction to deposit a single shifted bit directly into the n-th set bit of your bitboard, then counts the trailing zeros. It’s $O(1)$ and insanely fast, but it requires a CPU with BMI2 support (Intel Haswell+, AMD Zen 3+).

3 Likes
4

Fantastic!
asm far beyond my skillset :wink:

1 Like
5

I might be wrong but i feel like there is a native method to get the first set bit in a integer.

The count leading zeros function will give you the index of the next 1 bit. well you’d have to use the bit size of the type to clear it. but this would be fairly efficient to put into a loop. and it uses fast assembly instructions if they are available.

6

@clz is the opposite of @ctz. What I needed it the nth bit. Not the LSB or MSB.

7

You can use @ctz to find the nth 1 bit. See the next function in BitSetIterator here:
https://ziglang.org/documentation/master/std/#src/std/bit_set.zig

If you’re using the std bit set, you could just call the iterator’s next function n times. Or you could copy and modify the iterator code to fit your needs.