Loading learning content...
After exploring manual algorithms—from naive iteration through Kernighan's elegant approach to the parallel SWAR technique—we arrive at a practical question: In production code, how should you actually count bits?
The answer, in nearly all cases, is to use built-in functions. Modern programming languages provide optimized bit-counting operations that leverage hardware instructions when available and fall back to efficient software implementations otherwise. These built-ins represent decades of optimization work by language implementers and CPU designers.
This page surveys the bit-counting landscape across major programming languages, examines the hardware instructions that make sub-nanosecond popcount possible, and provides guidance on making the right choice for your context.
By the end of this page, you will know the built-in popcount functions in Python, JavaScript/TypeScript, Java, C++, Rust, and Go. You'll understand hardware POPCNT instructions, compiler intrinsics, and how to make informed decisions about when to use built-ins versus manual implementations.
Before surveying specific languages, let's understand why built-in functions are the preferred choice for production code.
Performance:
Built-in popcount functions typically compile to a single CPU instruction on modern processors. The POPCNT instruction on x86-64 and the CNT instruction on ARM execute in 1-3 CPU cycles—far faster than any software implementation.
Correctness:
Built-in functions are exhaustively tested by language implementers. They handle edge cases (negative numbers, overflow, different integer sizes) correctly. Manual implementations often contain subtle bugs that only manifest in production.
Maintainability:
Code using n.bit_count() or Integer.bitCount(n) is immediately clear to any reader. A 10-line SWAR implementation requires comments, documentation, and reader effort.
Portability:
Language built-ins automatically choose the best implementation for the target platform. They use hardware instructions when available and efficient fallbacks otherwise. Manual code must either target a specific platform or include multiple implementations.
| Aspect | Built-in Functions | Manual Implementation |
|---|---|---|
| Performance | Optimal (often 1 CPU instruction) | Good at best, often 10-50x slower |
| Correctness | Extensively tested, all edge cases handled | Prone to subtle bugs |
| Readability | Self-documenting function call | Requires comments and documentation |
| Portability | Automatic platform optimization | Platform-specific or fallback-only |
| Maintenance | Zero maintenance needed | Must update for new platforms |
In 90%+ of cases, use the built-in function. Only implement popcount manually when: (1) you're in an interview and asked to, (2) you're on a platform without built-ins, (3) you need to process bits individually anyway, or (4) you're learning/teaching the algorithms.
Modern CPUs include dedicated circuitry for counting bits. Understanding these instructions helps you appreciate why built-in functions are so fast.
x86-64: POPCNT Instruction
Introduced with Intel Nehalem (2008) and AMD Barcelona (2007), the POPCNT instruction counts set bits in a 16, 32, or 64-bit register in a single operation.
ARM: CNT Instruction
ARM's NEON SIMD extension includes the CNT instruction for population count, available on ARMv7 and later (including all modern smartphones).
RISC-V: CPOP Instruction
The RISC-V "B" (Bitmanip) extension includes CPOP (count population) for efficient bit counting.
How Fast is Hardware?
Consider counting bits in a billion integers:
Hardware is 10-100x faster than any software alternative!
1234567891011121314151617181920212223242526272829303132
// What the POPCNT instruction looks like at the assembly level // x86-64 assembly for popcount:// popcnt rax, rdi ; Count bits in rdi, store result in rax // The C++ compiler generates this when using:#include <bit>int count = std::popcount(value); // Or with compiler intrinsics:int count = __builtin_popcount(value); // 32-bitint count = __builtin_popcountll(value); // 64-bit // The entire software implementation collapses to ONE instruction! // Checking if POPCNT is available at compile time:#ifdef __POPCNT__ // Safe to use hardware popcount #define POPCOUNT(x) __builtin_popcount(x)#else // Fall back to software #define POPCOUNT(x) popcount_swar(x)#endif // Checking at runtime (for libraries that must run everywhere):#include <cpuid.h>bool has_popcnt() { unsigned int eax, ebx, ecx, edx; __cpuid(1, eax, ebx, ecx, edx); return (ecx & (1 << 23)) != 0; // POPCNT flag in ECX bit 23}Modern compilers can sometimes recognize popcount patterns and automatically generate POPCNT instructions. GCC and Clang may transform a well-written SWAR implementation into a single POPCNT when optimizations are enabled and the target supports it. However, using explicit built-ins is more reliable.
Python provides clean, Pythonic ways to count bits, with the preferred method depending on your Python version.
Python 3.10+ (Recommended): int.bit_count()
Introduced in Python 3.10, bit_count() is a method on integer objects that returns the number of set bits. It's implemented in C and uses optimized algorithms based on the platform.
All Python Versions: bin(n).count('1')
Before Python 3.10, the common idiom was to convert to a binary string and count '1' characters. This is less efficient but universally available.
Arbitrary Precision:
Python's integers have unlimited precision, and bit_count() works on arbitrarily large numbers—something not possible with fixed-width hardware instructions.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
# =============================================# Python 3.10+ Recommended: bit_count()# ============================================= def popcount_modern(n: int) -> int: """ Use the built-in bit_count() method. This is the cleanest and typically fastest approach. Works for negative numbers (uses absolute value representation). """ return n.bit_count() # Examples:print((7).bit_count()) # 3print((255).bit_count()) # 8print((0).bit_count()) # 0 # Works for arbitrarily large integers!huge_number = 2**1000 - 1 # 1000 consecutive 1 bitsprint(huge_number.bit_count()) # 1000 # =============================================# All Python Versions: bin().count()# ============================================= def popcount_universal(n: int) -> int: """ Convert to binary string and count '1' characters. Works on all Python versions. Less efficient but universally available. """ if n < 0: # Handle negative numbers (two's complement representation) # This matches the bit pattern, not the mathematical concept raise ValueError("Negative numbers require special handling") return bin(n).count('1') # Note: bin() returns strings like '0b1101' # The '0b' prefix doesn't contain '1', so it's safe # =============================================# Handling Negative Numbers# ============================================= def popcount_with_negatives(n: int, bits: int = 32) -> int: """ Count bits treating n as a fixed-width two's complement integer. Python's native integers are arbitrary precision, so negative numbers have conceptually infinite leading 1 bits. This function treats them as fixed-width. """ if n < 0: # Convert to unsigned representation n = n & ((1 << bits) - 1) return n.bit_count() if hasattr(n, 'bit_count') else bin(n).count('1') # Example:print(popcount_with_negatives(-1, 32)) # 32 (all bits set)print(popcount_with_negatives(-1, 8)) # 8 # =============================================# Performance Comparison# ============================================= import timeit def benchmark(): """Compare different popcount methods.""" n = 0xDEADBEEF # Method 1: bit_count() (Python 3.10+) t1 = timeit.timeit(lambda: n.bit_count(), number=1000000) # Method 2: bin().count() t2 = timeit.timeit(lambda: bin(n).count('1'), number=1000000) # Method 3: Kernighan (manual) def kernighan(x): c = 0 while x: x &= x - 1 c += 1 return c t3 = timeit.timeit(lambda: kernighan(n), number=1000000) print(f"bit_count(): {t1:.3f}s") print(f"bin().count(): {t2:.3f}s") print(f"Kernighan: {t3:.3f}s") # Typical results show bit_count() is 2-5x faster than bin().count() # =============================================# Related Methods# ============================================= # bit_length() - Number of bits needed to represent the valueprint((255).bit_length()) # 8 (binary: 11111111)print((256).bit_length()) # 9 (binary: 100000000) # Relationship for powers of two:# If n is a power of 2: bit_count(n) == 1 and bit_length(n) == log2(n) + 1n = 64 # 2^6 = 0b1000000print(n.bit_count()) # 1print(n.bit_length()) # 7 (position of highest bit + 1)JavaScript historically lacked a built-in popcount function, though modern approaches are improving. Here's the current landscape:
No Native Method (as of 2024):
Unlike Python or Java, JavaScript's Number and BigInt types don't have a native bitCount() or equivalent method. You must implement it yourself or use a library.
Recommended Approaches:
bin().count()Bitwise Limitation:
JavaScript's bitwise operators (&, |, ^, ~, <<, >>, >>>) convert operands to 32-bit signed integers. This means you can't use SWAR directly on numbers larger than 2³¹ - 1 without BigInt.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124
// =============================================// JavaScript/TypeScript Popcount Implementations// ============================================= /** * SWAR popcount for 32-bit integers. * * This is the fastest software approach for numbers * that fit in JavaScript's 32-bit signed integer range. * * @param n - A 32-bit integer * @returns Number of set bits */function popcount32(n: number): number { // Ensure 32-bit unsigned semantics n = n >>> 0; // Convert to unsigned 32-bit // SWAR algorithm n = n - ((n >>> 1) & 0x55555555); n = (n & 0x33333333) + ((n >>> 2) & 0x33333333); n = (n + (n >>> 4)) & 0x0F0F0F0F; return (n * 0x01010101) >>> 24;} /** * String-based popcount (slower but simple). * * Works for any non-negative integer in JavaScript's safe range. */function popcountString(n: number): number { if (n < 0) { throw new Error("Negative numbers require special handling"); } return n.toString(2).split('1').length - 1; // Or equivalently: // return (n.toString(2).match(/1/g) || []).length;} /** * Kernighan's algorithm for JavaScript. * * Works within 32-bit range; use BigInt version for larger. */function popcountKernighan(n: number): number { n = n >>> 0; // Convert to unsigned 32-bit let count = 0; while (n) { n = (n & (n - 1)) >>> 0; // Clear rightmost bit count++; } return count;} /** * BigInt popcount for arbitrary precision. * * Necessary for numbers > 2^53 - 1 (JavaScript's safe integer limit). */function popcountBigInt(n: bigint): number { if (n < 0n) { throw new Error("Negative BigInt requires special handling"); } let count = 0; while (n > 0n) { n = n & (n - 1n); count++; } return count;} // =============================================// Usage Examples// ============================================= console.log(popcount32(0b11010111)); // 6console.log(popcount32(0xFFFFFFFF)); // 32console.log(popcount32(-1 >>> 0)); // 32 (all bits set) console.log(popcountString(255)); // 8console.log(popcountBigInt(2n ** 100n - 1n)); // 100 // =============================================// Type-safe wrapper with best method selection// ============================================= function popcount(n: number | bigint): number { if (typeof n === 'bigint') { return popcountBigInt(n); } // For regular numbers, use SWAR for 32-bit range if (Number.isInteger(n) && n >= 0 && n <= 0xFFFFFFFF) { return popcount32(n); } // Fallback to string method for larger safe integers return popcountString(n);} // =============================================// Performance Comparison// ============================================= function benchmark(): void { const n = 0xDEADBEEF; const iterations = 1000000; console.time('SWAR'); for (let i = 0; i < iterations; i++) popcount32(n); console.timeEnd('SWAR'); console.time('String'); for (let i = 0; i < iterations; i++) popcountString(n); console.timeEnd('String'); console.time('Kernighan'); for (let i = 0; i < iterations; i++) popcountKernighan(n); console.timeEnd('Kernighan');} // Typical results: SWAR ≈ 2-10x faster than string methodJavaScript Numbers are 64-bit floats. Integers above 2^53 - 1 (Number.MAX_SAFE_INTEGER) lose precision. For large integers, use BigInt. For popcount on 32-bit values, the >>> 0 coercion ensures correct unsigned behavior.
Java provides excellent built-in support for bit counting through wrapper class methods.
Integer.bitCount(int i):
Counts the number of one-bits in a 32-bit integer. Uses an optimized SWAR algorithm that compiles to the POPCNT instruction on supporting CPUs.
Long.bitCount(long l):
Counts the number of one-bits in a 64-bit long integer. Same optimizations as Integer.bitCount.
Historical Note:
These methods were added in Java 1.5 (2004). Before that, developers had to implement popcount manually. The source code of Integer.bitCount is the canonical SWAR implementation seen in many textbooks.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
/** * Java Built-in Bit Counting Methods */public class JavaBitCount { public static void main(String[] args) { // ============================================= // Integer.bitCount() - 32-bit integers // ============================================= System.out.println(Integer.bitCount(0b11010111)); // 6 System.out.println(Integer.bitCount(0)); // 0 System.out.println(Integer.bitCount(-1)); // 32 (all bits set) System.out.println(Integer.bitCount(0xFFFFFFFF)); // 32 System.out.println(Integer.bitCount(0x12345678)); // 13 // ============================================= // Long.bitCount() - 64-bit integers // ============================================= System.out.println(Long.bitCount(0xDEADBEEFCAFEBABEL)); // 48 System.out.println(Long.bitCount(-1L)); // 64 // ============================================= // Related Methods // ============================================= // Number of leading zeros System.out.println(Integer.numberOfLeadingZeros(16)); // 27 // Number of trailing zeros System.out.println(Integer.numberOfTrailingZeros(16)); // 4 // Highest one bit (isolate) System.out.println(Integer.highestOneBit(100)); // 64 (0b1100100 → 0b1000000) // Lowest one bit (isolate) System.out.println(Integer.lowestOneBit(100)); // 4 (0b1100100 → 0b0000100) // Reverse bits System.out.println(Integer.toBinaryString( Integer.reverse(0b10110000_00000000_00000000_00000001) )); // 10000000000000000000000000001101 // ============================================= // BigInteger for arbitrary precision // ============================================= var big = new java.math.BigInteger("2").pow(1000).subtract( java.math.BigInteger.ONE ); System.out.println(big.bitCount()); // 1000 // ============================================= // What Integer.bitCount Actually Does // ============================================= // This is the actual implementation from OpenJDK: // (Shown for educational purposes - always use the built-in!) int i = 0b11010111; // SWAR algorithm: i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); int result = i & 0x3f; System.out.println("Manual SWAR result: " + result); // 6 } // ============================================= // Practical Example: Hamming Distance // ============================================= /** * Calculate Hamming distance between two integers. * Uses built-in bitCount on XOR result. */ public static int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); } /** * Check if n is a power of two using bitCount. * (Alternative to n & (n-1) == 0) */ public static boolean isPowerOfTwo(int n) { return n > 0 && Integer.bitCount(n) == 1; }}The HotSpot JIT compiler recognizes Integer.bitCount() and can replace it with a POPCNT instruction on CPUs that support it. This means Java's built-in is not just convenient—it's as fast as native code. Always prefer Integer.bitCount() over manual implementations.
C++ offers multiple approaches to bit counting, from portable standard library functions to compiler-specific intrinsics.
C++20: std::popcount (Recommended)
The <bit> header introduced in C++20 provides std::popcount as a standard, portable function. It works with any unsigned integer type and leverages hardware when available.
Compiler Intrinsics (Pre-C++20):
__builtin_popcount(), __builtin_popcountl(), __builtin_popcountll()__popcnt(), __popcnt16(), __popcnt64() (requires <intrin.h>)Related C++20 Functions:
std::has_single_bit(n) — Is n a power of two?std::countl_zero(n) — Count leading zerosstd::countr_zero(n) — Count trailing zerosstd::countl_one(n) — Count leading onesstd::countr_one(n) — Count trailing ones123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
#include <bit> // C++20: std::popcount, std::has_single_bit#include <cstdint>#include <iostream>#include <type_traits> // =============================================// C++20: Standard Library (Recommended)// ============================================= void demo_cpp20() { // std::popcount works with any unsigned integer type std::cout << std::popcount(0b11010111u) << std::endl; // 6 std::cout << std::popcount(0xFFFFFFFFu) << std::endl; // 32 std::cout << std::popcount(0xDEADBEEFCAFEBABEull) << std::endl; // 48 // std::has_single_bit - power of two check std::cout << std::has_single_bit(16u) << std::endl; // true (1) std::cout << std::has_single_bit(15u) << std::endl; // false (0) // Related bit manipulation functions uint32_t n = 0b00010100u; // = 20 std::cout << std::countl_zero(n) << std::endl; // 27 (leading zeros) std::cout << std::countr_zero(n) << std::endl; // 2 (trailing zeros) // Round up to next power of two std::cout << std::bit_ceil(20u) << std::endl; // 32 // Round down to previous power of two std::cout << std::bit_floor(20u) << std::endl; // 16} // =============================================// Pre-C++20: Compiler Intrinsics// ============================================= // Cross-platform wrapperinline int popcount_portable(uint32_t n) {#if defined(__cpp_lib_bitops) // C++20 available return std::popcount(n);#elif defined(__GNUC__) || defined(__clang__) return __builtin_popcount(n);#elif defined(_MSC_VER) return __popcnt(n); // Requires <intrin.h>#else // Fallback: SWAR implementation n = n - ((n >> 1) & 0x55555555); n = (n & 0x33333333) + ((n >> 2) & 0x33333333); n = (n + (n >> 4)) & 0x0F0F0F0F; return (n * 0x01010101) >> 24;#endif} // 64-bit versioninline int popcount_portable_64(uint64_t n) {#if defined(__cpp_lib_bitops) return std::popcount(n);#elif defined(__GNUC__) || defined(__clang__) return __builtin_popcountll(n);#elif defined(_MSC_VER) return __popcnt64(n);#else // Fallback: SWAR for 64-bit n = n - ((n >> 1) & 0x5555555555555555ULL); n = (n & 0x3333333333333333ULL) + ((n >> 2) & 0x3333333333333333ULL); n = (n + (n >> 4)) & 0x0F0F0F0F0F0F0F0FULL; return (n * 0x0101010101010101ULL) >> 56;#endif} // =============================================// Template version for any unsigned type// ============================================= template<typename T>requires std::is_unsigned_v<T>constexpr int popcount_generic(T n) {#if __cpp_lib_bitops >= 201907L return std::popcount(n);#else int count = 0; while (n) { n &= n - 1; ++count; } return count;#endif} // =============================================// Compile-time popcount (constexpr)// ============================================= // std::popcount is constexpr in C++20!constexpr int KNOWN_COUNT = std::popcount(0x12345678u); // Computed at compile time static_assert(std::popcount(7u) == 3, "Compile-time check");static_assert(std::has_single_bit(64u), "64 is power of 2"); int main() { demo_cpp20(); std::cout << "Portable 32-bit: " << popcount_portable(0xDEADBEEF) << std::endl; std::cout << "Portable 64-bit: " << popcount_portable_64(0xDEADBEEFCAFEBABE) << std::endl; std::cout << "Compile-time: " << KNOWN_COUNT << std::endl; return 0;}std::popcount only accepts unsigned integer types. If you have a signed integer, cast it: std::popcount(static_cast<uint32_t>(n)). This is intentional—signed integers have implementation-defined representation, so popcount semantics would be ambiguous.
Let's survey popcount support in other popular languages.
Rust provides count_ones() as a method on all integer types. It's stable, optimized, and uses hardware instructions when available.
123456789101112131415161718192021222324252627
fn main() { // count_ones() is available on all integer types let n: u32 = 0b11010111; println!("{}", n.count_ones()); // 6 // Works with different sizes let a: u8 = 0xFF; let b: u64 = 0xDEADBEEFCAFEBABE; println!("{}", a.count_ones()); // 8 println!("{}", b.count_ones()); // 48 // Related methods let x: u32 = 0b00010100; println!("Leading zeros: {}", x.leading_zeros()); // 27 println!("Trailing zeros: {}", x.trailing_zeros()); // 2 println!("Leading ones: {}", (!x).leading_ones()); // 0 // Is power of two? println!("16 is power of 2: {}", 16u32.is_power_of_two()); // true // Next power of two println!("Next power of 2 after 20: {}", 20u32.next_power_of_two()); // 32 // count_zeros() for complement println!("Zeros in 0xFF_u8: {}", 0xFFu8.count_zeros()); // 0 println!("Zeros in 0xF0_u8: {}", 0xF0u8.count_zeros()); // 4}We've surveyed the landscape of built-in popcount functions across languages and hardware. Here are the essential takeaways:
| Language | Function | Availability |
|---|---|---|
| Python | n.bit_count() | 3.10+ |
| Java | Integer.bitCount(n) | 1.5+ |
| C++ | std::popcount(n) | C++20 |
| C++ (GCC) | __builtin_popcount(n) | Always |
| Rust | n.count_ones() | Stable |
| Go | bits.OnesCount(n) | 1.9+ |
| C# | BitOperations.PopCount(n) | .NET Core 3.0+ |
Module Complete:
Congratulations! You've completed the "Power of Two & Counting Bits" module. You now understand:
n & (n-1) == 0These techniques form the foundation for more advanced bit manipulation patterns covered in subsequent modules.
You've mastered the essential techniques for detecting powers of two and counting set bits. From mathematical foundations to practical language-specific implementations, you now have a complete toolkit for these fundamental bit manipulation operations. Apply this knowledge in hash tables, memory allocation, error detection, and countless other domains!