How to find the Nth set bit in a 32‑bit integer with C

1 Answer

0 votes
#include <stdio.h>
#include <stdint.h>

/*
    findNthSetBit32:
    ----------------
    Given:
        - x : a 32-bit integer
        - n : which set bit to find (1-based index)

    Returns:
        A 32-bit mask with ONLY the Nth set bit of x turned on.
        If n is larger than the number of set bits, returns 0.

    Algorithm:
        - Use __builtin_ctz(x) to locate the lowest set bit (index 0–31).
        - Remove that bit using x &= (x - 1).
        - When we reach the Nth one, return 1u << index.

    Notes:
        - __builtin_ctz(x) is a built‑in function that counts trailing zeros.
          It is extremely efficient and maps to a single CPU instruction
          (e.g., TZCNT or BSF on x86).
        - Behavior is undefined for x == 0, but we never call it when x == 0.
*/
uint32_t findNthSetBit32(uint32_t x, unsigned n)
{
    while (x != 0) {

        // Index of lowest set bit
        unsigned index = __builtin_ctz(x);

        // If this is the Nth set bit, return a mask with ONLY that bit set
        if (--n == 0)
            return 1u << index;

        // Remove the lowest set bit
        x &= (x - 1);
    }

    // Fewer than n set bits
    return 0;
}

int main(void)
{
    uint32_t value = 0b00001101001101101100100010100000u;
    unsigned n = 4;

    uint32_t result = findNthSetBit32(value, n);

    printf("Input value:  %032b\n", value);
    printf("N = %u\n", n);
    printf("Result mask:  %032b\n", result);

    return 0;
}


/*
run:

Input value:  00001101001101101100100010100000
N = 4
Result mask:  00000000000000000100000000000000

*/

 



answered Jul 24 by avibootz
...