Bit Manipulation in TheAlgorithms/Python

The naive approach to counting set bits loops over every bit position and checks each one, taking O(W) time where W is the word width. Brian Kernighan's method runs the loop only as many times as there are set bits. The identity n &= n - 1 works because subtracting 1 from n propagates a borrow that flips the lowest set bit to 0 and sets all lower bits to 1. ANDing the original n with this value zeroes the lowest set bit and leaves higher bits unchanged. The file's comment captures this exactly: the loop will only run the number of 1 times. For sparse integers, such as those produced by permission bitmasks or sparse feature vectors, this is substantially faster than scanning every bit position. The technique is documented in Kernighan and Ritchie's The C Programming Language and cited in the docstring's reference URL.

Compilers and embedded systems code manipulate individual bits inside registers and status words constantly. This file provides four composable building blocks: set_bit, clear_bit, flip_bit, and is_bit_set. Each one builds a mask by left-shifting the integer literal 1 to the target position, creating a number that is zero in every bit except position. The four operations then differ only in which bitwise operator they apply. Set uses OR so the target bit becomes 1 regardless of its current value. Clear uses AND with the bitwise NOT of the mask so the target bit becomes 0 regardless. Flip uses XOR because XOR with 1 inverts any bit. Test shifts the target bit to position 0 and ANDs with 1 to extract its value as a boolean. The doctest for set_bit(0b1101, 1) produces 15, which is 0b1111, confirming the second bit was set.

Bit reversal is used in fast Fourier transform butterfly stages, CRC polynomial evaluation, and certain hash functions. The correct approach for a fixed 32-bit width runs a loop exactly 32 times and uses no lookup table. Each iteration makes progress simultaneously on both integers: the input loses its lowest bit via a right shift, and the result gains that bit at its current top position via a left shift followed by OR. The key invariant is that after k iterations, the result holds the reversed version of the k least significant bits of the original input and the k most significant bit positions of the result are occupied. The doctest confirms: reverse_bit(25) returns 2,550,136,832, and reverse_bit(2550136832) returns 25, demonstrating that the operation is its own inverse.

Finding the single non-duplicate element in a list where every other value appears exactly twice looks like it requires a hash set for O(n) time and O(n) space. XOR collapses this to O(n) time and O(1) space by exploiting two properties of XOR: a ^ a == 0 (any value XORed with itself is zero) and a ^ 0 == a (any value XORed with zero is itself). Folding the entire list with XOR means every pair cancels to 0, and 0 XORed with the singleton is the singleton. The doctest confirms: find_unique_number([1, 1, 2, 2, 3]) returns 3 because both 1s and both 2s cancel. This is not a trick specific to integers; the same pattern applies to any abelian group where every element is its own inverse, which is exactly the structure XOR provides over fixed-width bit patterns.

Powers of two have exactly one bit set, which makes them recognizable in constant time without iteration. Subtracting one from a power of two flips that single set bit to zero and turns every lower zero into a one, so n & (n - 1) equals zero only when no other bits are set. Lines 32 and 33 reject negative inputs because the same check would silently misclassify two's-complement representations of negative numbers. The single return on line 34 (number & (number - 1) == 0) is the entire decision: positive inputs that are powers of two zero out, everything else leaves at least one bit standing. The doctests cover 0, 1, 2, 4, 6, 8, 17, and a 64-bit value to verify the boundary cases and confirm that 0 is treated as not-a-power-of-two via the lone n > 0 guard.

Gray code is used wherever binary counting would cause multiple bits to change simultaneously, most notably in rotary encoders. The recursive construction exploits the reflection property: take the (n-1)-bit Gray code sequence, prepend '0' to each element of the first half, and prepend '1' to each element of the second half traversed in reverse. The reversal is the key. The last element of the '0' half and the first element of the '1' half are the same (n-1)-bit string, so prepending '0' versus '1' makes them differ by exactly one bit. The wrap-around pair also differs by one bit for the same reason. The outer gray_code function converts the string list to integers with int(s, 2). The doctest for gray_code(2) returns [0, 1, 3, 2], binary 00, 01, 11, 10, confirming each adjacent pair differs by one bit position.