easy

Bit Counting Tricks

Implement three utilities on a non-negative 32-bit integer: count its 1 bits, decide whether it is a power of two, and isolate its lowest set bit. Each should run in time proportional to the number of set bits or better.

Constraints

0 ≤ x < 2^32

Examples

in: x = 12 (1100b)

out: popcount = 2, isPowerOfTwo = false, lowestBit = 4

in: x = 16

out: popcount = 1, isPowerOfTwo = true, lowestBit = 16

Recognition clues

x & (x − 1) clears the lowest set bit
A power of two has exactly one set bit
x & -x isolates the lowest set bit via two's complement

Pattern

Bit Manipulation

XOR cancels pairs, so "every element appears twice except one" is a single XOR pass with no extra memory. Sets of at most ~20 items fit in an integer bitmask, turning subset enumeration and "which nodes have been visited" states into cheap arithmetic that DP and BFS can index directly.

Count Set Bits (Popcount)Power-of-Two Tricks Set, Clear, Toggle & Test a Bit Bitwise Operators

Solution

Popcount: loop x &= x - 1 until zero, counting iterations — each step removes one set bit. Power of two: x > 0 && (x & (x - 1)) == 0, because a single set bit becomes zero after one clear. Lowest set bit: x & -x, since negation flips all bits above the lowest set bit and keeps it. These identities underpin Fenwick trees and subset enumeration.

time O(popcount) or O(1)space O(1)

Alternative approaches

Lookup tables per byte or the hardware popcnt instruction give constant time. Iterating all 32 bits is simpler but slower.

Code it yourself

Solve in

Hints:

Learn XOR Patterns ▶ Visualize