#include <bitset>
#include <cstdint>
#include <iostream>

/***************************************************
 * Clearing the least significant 1 bit
 *
 * Write a function that clears the least significant
 * 1 bit in a 64-bit unsigned integer.
 *
 * For example, suppose
 *
 *     n = ...00101100.
 *
 * The least significant 1 bit is
 *
 *     n = ...00101100
 *                 ^
 *
 * Clearing this bit gives
 *
 *         ...00101000.
 *
 *
 * SUBTRACTING ONE
 *
 * Consider what happens when we subtract 1 from n.
 *
 * Beginning with the least significant 1 bit:
 *
 *   - that 1 becomes 0, and
 *   - all 0 bits to its right become 1.
 *
 * For example,
 *
 *     n     = ...00101100
 *     n - 1 = ...00101011.
 *
 * Notice that all bits to the left of the least
 * significant 1 bit remain unchanged.
 *
 *
 * USING BITWISE AND
 *
 * Now calculate
 *
 *     n & (n - 1).
 *
 * For our example,
 *
 *       ...00101100
 *     & ...00101011
 *       -----------
 *       ...00101000.
 *
 * The least significant 1 bit has been cleared,
 * while every other bit remains unchanged.
 *
 * Thus,
 *
 *     n & (n - 1)
 *
 * clears the least significant 1 bit of n.
 *
 *
 * WHAT HAPPENS WHEN n == 0?
 *
 * For an unsigned integer, subtracting 1 from 0
 * wraps around to the largest representable value:
 *
 *     0 - 1 = 0xffffffffffffffff.
 *
 * Consequently,
 *
 *     0 & (0 - 1) == 0.
 *
 * Thus, the function also returns 0 when n == 0.
 *
 *
 * AN IMPORTANT APPLICATION
 *
 * Each call to clear_least_1 removes exactly one
 * 1 bit.
 *
 * Therefore, repeatedly applying this operation
 * until the value becomes zero requires exactly as
 * many iterations as there are 1 bits in the
 * original value.
 *
 * This gives us another way to count the number of
 * 1 bits in an integer.
 ***************************************************/

// Function declarations
int main();
std::uint64_t clear_least_1( std::uint64_t n );

// Function definitions
int main() {
    std::uint64_t n{
        UINT64_C( 0x0123456789abcdef )
    };

    while ( n != 0 ) {
        std::cout << std::bitset<64>( n )
                  << std::endl;

        n = clear_least_1( n );
    }

    std::cout << std::bitset<64>( n )
              << std::endl;

    return 0;
}

/***************************************************
 * clear_least_1
 *
 * Clears the least significant 1 bit in n.
 *
 * If n == 0, the function returns 0.
 ***************************************************/
std::uint64_t clear_least_1( std::uint64_t n ) {
    return n & (n - 1);
}