#include <iostream>
#include <cstdint>
#include <bitset>
/*
findNthSetBit:
---------------
Given:
- x : a 64-bit 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:
- Repeatedly locate the lowest set bit using std::countr_zero.
- Remove that bit using x &= (x - 1).
- When we reach the Nth one, return a mask with that bit set.
*/
std::uint64_t findNthSetBit(std::uint64_t x, unsigned n)
{
while (x != 0) {
// Find index of lowest set bit (0–63)
unsigned index = std::countr_zero(x);
// If this is the Nth set bit, return a mask with only that bit set
if (--n == 0)
return 1ULL << index;
// Remove the lowest set bit
x &= (x - 1);
}
// If we run out of bits before reaching n, return 0
return 0;
}
int main()
{
std::uint64_t value =
0b0000000000000000000010000000000000001101001101101100100010100000ULL;
unsigned n = 4; // Find the 4th set bit
std::uint64_t result = findNthSetBit(value, n);
std::cout << "Input value: " << std::bitset<64>(value) << "\n";
std::cout << "N = " << n << "\n";
std::cout << "Result mask: " << std::bitset<64>(result) << "\n";
std::cout << "\n";
}
/*
run:
Input value: 0000000000000000000010000000000000001101001101101100100010100000
N = 4
Result mask: 0000000000000000000000000000000000000000000000000100000000000000
*/
