#include <stdio.h>
#include <stdint.h>
/*
findNthSetBit64:
----------------
Given:
- x : a 64-bit unsigned integer
- n : which set bit to find (1-based index)
Returns:
A 64-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_ctzll(x) to locate the lowest set bit.
- Remove that bit using x &= (x - 1).
- When we reach the Nth one, return 1ULL << index.
Notes:
- __builtin_ctzll(x) returns the number of trailing zeros (0–63).
- It maps to a single CPU instruction (TZCNT/BSF) on most systems.
*/
uint64_t findNthSetBit64(uint64_t x, unsigned n)
{
while (x != 0) {
// Index (0–63) of the lowest set bit
unsigned index = __builtin_ctzll(x);
// If this is the Nth set bit, return mask
if (--n == 0)
return 1ULL << index;
// Remove the lowest set bit
x &= (x - 1);
}
// Fewer than n set bits
return 0ULL;
}
/*
toBinary64:
-----------
Convert a 64-bit integer to a padded 64-bit binary string.
*/
void toBinary64(uint64_t x, char out[65])
{
for (int i = 63; i >= 0; --i)
out[63 - i] = ((x >> i) & 1ULL) ? '1' : '0';
out[64] = '\0';
}
int main(void)
{
uint64_t value =
0b0000000000000000000010000000000000001101001101101100100010100000ULL;
unsigned n = 4;
uint64_t result = findNthSetBit64(value, n);
char binValue[65], binResult[65];
toBinary64(value, binValue);
toBinary64(result, binResult);
printf("Input value: %s\n", binValue);
printf("N = %u\n", n);
printf("Result mask: %s\n", binResult);
return 0;
}
/*
run:
Input value: 0000000000000000000010000000000000001101001101101100100010100000
N = 4
Result mask: 0000000000000000000000000000000000000000000000000100000000000000
*/
