Run your code 2 more times to open the solutions. The idea sticks better after an attempt. Counting Bits in Python
3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.
For every i from 0 to n, copy it into x and peel bits off the right end: x & 1 is the last bit and x >>= 1 drops it. The loop stops when x reaches 0, so each number costs one step per binary digit, about log₂ n.
def count_bits(n: int) -> list[int]:
result = []
for i in range(n + 1):
x, ones = i, 0
while x:
ones += x & 1
x >>= 1
result.append(ones)
return result
i >> 1 is i with its last bit removed, so it has the same 1 bits except possibly that one. Its count is already in the list because i >> 1 is smaller than i, and the missing bit is i & 1. One addition per entry fills the table in linear time.
def count_bits(n: int) -> list[int]:
bits = [0] * (n + 1)
for i in range(1, n + 1):
bits[i] = bits[i >> 1] + (i & 1)
return bits
i & (i - 1) clears the lowest 1 bit of i: 12 (1100) becomes 8 (1000). That number is smaller and has exactly one 1 bit fewer, so the count for i is its count plus one. Starting at 1 keeps i - 1 from going negative.
def count_bits(n: int) -> list[int]:
bits = [0] * (n + 1)
for i in range(1, n + 1):
bits[i] = bits[i & (i - 1)] + 1
return bits
Counting Bits in JavaScript
3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.
For every i, a while loop adds the last bit x & 1 and shifts it away with x >>= 1 until nothing is left. Each number takes one step per binary digit, so the whole run is O(n log n).
function countBits(n) {
const result = [];
for (let i = 0; i <= n; i++) {
let x = i;
let ones = 0;
while (x !== 0) {
ones += x & 1;
x >>= 1;
}
result.push(ones);
}
return result;
}
i >> 1 is i without its last bit, and its count sits earlier in the array. Add the dropped bit i & 1 and the entry is done. new Array(n + 1).fill(0) sets every slot to 0 up front, so bits[0] is already right.
function countBits(n) {
const bits = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
i & (i - 1) is i with its lowest 1 bit cleared, a smaller number with exactly one 1 bit fewer. Its count plus one is the count for i, again one lookup per entry.
function countBits(n) {
const bits = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
Counting Bits in TypeScript
3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.
For every i, add the last bit x & 1 and shift it away with x >>= 1 until x is 0. One step per binary digit makes the whole run O(n log n).
function countBits(n: number): number[] {
const result: number[] = [];
for (let i = 0; i <= n; i++) {
let x = i;
let ones = 0;
while (x !== 0) {
ones += x & 1;
x >>= 1;
}
result.push(ones);
}
return result;
}
i >> 1 is i without its last bit and was filled earlier, so the count for i is that entry plus i & 1. The number[] table is the answer itself.
function countBits(n: number): number[] {
const bits: number[] = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
i & (i - 1) clears the lowest 1 bit of i, leaving a smaller number with one 1 bit fewer. Its count plus one is the count for i.
function countBits(n: number): number[] {
const bits: number[] = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
Counting Bits in Java
3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.
For every i, a while loop adds the last bit x & 1 and shifts it off with x >>>= 1. The unsigned shift fills with zeros, so the loop would end even for a negative value. One step per binary digit makes it O(n log n).
import java.util.*;
public class Main {
static int[] countBits(int n) {
int[] result = new int[n + 1];
for (int i = 0; i <= n; i++) {
int x = i;
int ones = 0;
while (x != 0) {
ones += x & 1;
x >>>= 1;
}
result[i] = ones;
}
return result;
}
}
i >> 1 is i without its last bit, and its count was stored earlier in the array. Adding i & 1 gives the count for i. A new int[] starts as zeros, so bits[0] needs no assignment.
import java.util.*;
public class Main {
static int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
}
i & (i - 1) clears the lowest 1 bit, giving a smaller number with exactly one 1 bit fewer. Its stored count plus one is the count for i.
import java.util.*;
public class Main {
static int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}
Counting Bits in Go
3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.
For every i, the inner for x > 0 loop adds the last bit x&1 and drops it with x >>= 1. make([]int, n+1) sizes the result once, and each number costs one step per binary digit.
package main
func countBits(n int) []int {
result := make([]int, n+1)
for i := 0; i <= n; i++ {
ones := 0
for x := i; x > 0; x >>= 1 {
ones += x & 1
}
result[i] = ones
}
return result
}
i>>1 is i without its last bit, and its count is already in the slice. Adding i&1 finishes the entry. make zeroes the slice, so bits[0] is right from the start.
package main
func countBits(n int) []int {
bits := make([]int, n+1)
for i := 1; i <= n; i++ {
bits[i] = bits[i>>1] + i&1
}
return bits
}
i&(i-1) clears the lowest 1 bit, giving a smaller number with exactly one 1 bit fewer. Its count plus one is the count for i.
package main
func countBits(n int) []int {
bits := make([]int, n+1)
for i := 1; i <= n; i++ {
bits[i] = bits[i&(i-1)] + 1
}
return bits
}
Counting Bits in C#
3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.
For every i, a while loop adds the last bit x & 1 and drops it with x >>= 1 until x is 0. Each number costs one step per binary digit, so the run is O(n log n).
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[] CountBits(int n)
{
var result = new int[n + 1];
for (int i = 0; i <= n; i++)
{
int x = i, ones = 0;
while (x != 0)
{
ones += x & 1;
x >>= 1;
}
result[i] = ones;
}
return result;
}
}
i >> 1 is i without its last bit, and its count was stored earlier. Adding i & 1 gives the count for i. A new int[] is zero-filled, so bits[0] is already right.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[] CountBits(int n)
{
var bits = new int[n + 1];
for (int i = 1; i <= n; i++)
{
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
}
i & (i - 1) clears the lowest 1 bit, leaving a smaller number with exactly one 1 bit fewer. Its count plus one is the count for i.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[] CountBits(int n)
{
var bits = new int[n + 1];
for (int i = 1; i <= n; i++)
{
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}
Counting Bits in C++
3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.
For every i, copy it into an unsigned and add the last bit x & 1 while shifting it away with x >>= 1. Shifting an unsigned value always fills with zeros, so the loop ends. Each number costs one step per binary digit.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> countBits(int n) {
vector<int> result(n + 1);
for (int i = 0; i <= n; i++) {
int ones = 0;
for (unsigned x = i; x != 0; x >>= 1) ones += x & 1;
result[i] = ones;
}
return result;
}
};
i >> 1 is i without its last bit, and its count is already in the vector. Adding i & 1 gives the count for i. vector<int> bits(n + 1) value-initialises every entry to 0.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> countBits(int n) {
vector<int> bits(n + 1);
for (int i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
};
i & (i - 1) clears the lowest 1 bit, giving a smaller number with exactly one 1 bit fewer. Its count plus one is the count for i.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> countBits(int n) {
vector<int> bits(n + 1);
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
};
Counting Bits in C
3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.
Allocate n + 1 ints and set *returnSize. For each i, copy it into an unsigned x, add the last bit x & 1 and shift it off with x >>= 1 until x is 0. Unsigned shifts fill with zeros, so the loop ends after at most 32 steps; one step per binary digit makes it O(n log n).
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
/**
* Note: the returned array must be malloc'ed; the caller frees it.
*/
int* countBits(int n, int* returnSize) {
int* result = malloc((n + 1) * sizeof *result);
*returnSize = n + 1;
for (int i = 0; i <= n; i++) {
unsigned x = (unsigned)i;
int ones = 0;
while (x != 0) {
ones += x & 1;
x >>= 1;
}
result[i] = ones;
}
return result;
}
calloc hands back zeroed memory, so bits[0] is already 0. Every later entry is the count of i >> 1, stored earlier because it is smaller, plus the bit that shift dropped, i & 1. The parentheses matter: + binds tighter than & in C.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
/**
* Note: the returned array must be malloc'ed; the caller frees it.
*/
int* countBits(int n, int* returnSize) {
int* bits = calloc(n + 1, sizeof *bits);
*returnSize = n + 1;
for (int i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
i & (i - 1) clears the lowest 1 bit of i, giving a smaller number with exactly one 1 bit fewer. Its stored count plus one is the count for i. The loop starts at 1, so i - 1 is never negative.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
/**
* Note: the returned array must be malloc'ed; the caller frees it.
*/
int* countBits(int n, int* returnSize) {
int* bits = calloc(n + 1, sizeof *bits);
*returnSize = n + 1;
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
Counting Bits in Kotlin
3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.
IntArray(n + 1) { … } fills each slot from a lambda. For every i, add the last bit x and 1 and shift it off with x ushr 1 until x is 0. One step per binary digit makes it O(n log n).
class Solution {
fun countBits(n: Int): IntArray = IntArray(n + 1) { i ->
var x = i
var ones = 0
while (x != 0) {
ones += x and 1
x = x ushr 1
}
ones
}
}
i shr 1 is i without its last bit, and its count is already in the array because it is smaller. Adding i and 1 gives the count for i. A new IntArray starts as zeros, so index 0 needs no assignment.
class Solution {
fun countBits(n: Int): IntArray {
val bits = IntArray(n + 1)
for (i in 1..n) {
bits[i] = bits[i shr 1] + (i and 1)
}
return bits
}
}
i and (i - 1) clears the lowest 1 bit, giving a smaller number with exactly one 1 bit fewer. Its stored count plus one is the count for i. For an n of 0 the range 1..0 is empty and the loop never runs.
class Solution {
fun countBits(n: Int): IntArray {
val bits = IntArray(n + 1)
for (i in 1..n) {
bits[i] = bits[i and (i - 1)] + 1
}
return bits
}
}
Counting Bits in Rust
3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.
Map every i in 0..=n to its count and collect into a Vec<i32>. The count copies i into a mutable x, adds the last bit x & 1 and shifts it off until x is 0, one step per binary digit.
impl Solution {
pub fn count_bits(n: i32) -> Vec<i32> {
(0..=n)
.map(|i| {
let mut x = i;
let mut ones = 0;
while x != 0 {
ones += x & 1;
x >>= 1;
}
ones
})
.collect()
}
}
vec![0; n + 1] starts every count at 0. Each entry is the count of i >> 1, stored earlier because it is smaller, plus the dropped bit i & 1. The loop runs over usize, so the index needs no cast and the bit becomes an i32 with as i32.
impl Solution {
pub fn count_bits(n: i32) -> Vec<i32> {
let n = n as usize;
let mut bits = vec![0; n + 1];
for i in 1..=n {
bits[i] = bits[i >> 1] + (i & 1) as i32;
}
bits
}
}
i & (i - 1) clears the lowest 1 bit, giving a smaller index with exactly one 1 bit fewer. Its count plus one is the count for i. The loop starts at 1, so i - 1 never underflows the usize, which would panic in a debug build.
impl Solution {
pub fn count_bits(n: i32) -> Vec<i32> {
let n = n as usize;
let mut bits = vec![0; n + 1];
for i in 1..=n {
bits[i] = bits[i & (i - 1)] + 1;
}
bits
}
}
Counting Bits in Swift
3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.
(0...n).map turns every i into its count. The closure copies i into a var x, adds the last bit x & 1 and shifts it off with x >>= 1 until x is 0, one step per binary digit.
class Solution {
func countBits(_ n: Int) -> [Int] {
return (0...n).map { i in
var x = i
var ones = 0
while x != 0 {
ones += x & 1
x >>= 1
}
return ones
}
}
}
[Int](repeating: 0, count: n + 1) starts every count at 0. Each entry is the count of i >> 1, stored earlier because it is smaller, plus the dropped bit i & 1. stride(from: 1, through: n, by: 1) is simply empty for an n of 0, where 1...n would trap.
class Solution {
func countBits(_ n: Int) -> [Int] {
var bits = [Int](repeating: 0, count: n + 1)
for i in stride(from: 1, through: n, by: 1) {
bits[i] = bits[i >> 1] + (i & 1)
}
return bits
}
}
i & (i - 1) clears the lowest 1 bit, giving a smaller index with exactly one 1 bit fewer. Its count plus one is the count for i. The same stride keeps an n of 0 from building the invalid range 1...0.
class Solution {
func countBits(_ n: Int) -> [Int] {
var bits = [Int](repeating: 0, count: n + 1)
for i in stride(from: 1, through: n, by: 1) {
bits[i] = bits[i & (i - 1)] + 1
}
return bits
}
}
Counting Bits in PHP
3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.
For every $i, copy it into $x, add the last bit $x & 1 and shift it off with $x >>= 1 until $x is 0. Appending with $result[] = builds a list in order, one step per binary digit.
<?php
class Solution {
/**
* @param int $n
* @return int[]
*/
function countBits(int $n): array {
$result = [];
for ($i = 0; $i <= $n; $i++) {
$x = $i;
$ones = 0;
while ($x !== 0) {
$ones += $x & 1;
$x >>= 1;
}
$result[] = $ones;
}
return $result;
}
}
$bits = [0] holds the count for 0. Each later entry is the count of $i >> 1, already in the array because it is smaller, plus the dropped bit $i & 1. Appending in order keeps the keys 0 to $n, so the result is a list.
<?php
class Solution {
/**
* @param int $n
* @return int[]
*/
function countBits(int $n): array {
$bits = [0];
for ($i = 1; $i <= $n; $i++) {
$bits[] = $bits[$i >> 1] + ($i & 1);
}
return $bits;
}
}
$i & ($i - 1) clears the lowest 1 bit, giving a smaller key with exactly one 1 bit fewer. Its stored count plus one is the count for $i.
<?php
class Solution {
/**
* @param int $n
* @return int[]
*/
function countBits(int $n): array {
$bits = [0];
for ($i = 1; $i <= $n; $i++) {
$bits[] = $bits[$i & ($i - 1)] + 1;
}
return $bits;
}
}
Counting Bits in Ruby
3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.
(0..n).map turns every i into its count. The block copies i into x, adds the last bit x & 1 and shifts it off with x >>= 1 until x is 0, one step per binary digit.
# @param {Integer} n
# @return {Integer[]}
def count_bits(n)
(0..n).map do |i|
x = i
ones = 0
while x != 0
ones += x & 1
x >>= 1
end
ones
end
end
Array.new(n + 1, 0) starts every count at 0. Each entry is the count of i >> 1, stored earlier because it is smaller, plus the dropped bit i & 1. 1.upto(n) does nothing when n is 0.
# @param {Integer} n
# @return {Integer[]}
def count_bits(n)
bits = Array.new(n + 1, 0)
1.upto(n) do |i|
bits[i] = bits[i >> 1] + (i & 1)
end
bits
end
i & (i - 1) clears the lowest 1 bit, giving a smaller index with exactly one 1 bit fewer. Its stored count plus one is the count for i.
# @param {Integer} n
# @return {Integer[]}
def count_bits(n)
bits = Array.new(n + 1, 0)
1.upto(n) do |i|
bits[i] = bits[i & (i - 1)] + 1
end
bits
end
Counting Bits in Dart
3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.
List.generate(n + 1, …) builds the list from a function of the index. For every i, add the last bit x & 1 and shift it off with x >>= 1 until x is 0, one step per binary digit.
class Solution {
List<int> countBits(int n) {
return List.generate(n + 1, (i) {
var x = i;
var ones = 0;
while (x != 0) {
ones += x & 1;
x >>= 1;
}
return ones;
});
}
}
List.filled(n + 1, 0) starts every count at 0. Each entry is the count of i >> 1, stored earlier because it is smaller, plus the dropped bit i & 1.
class Solution {
List<int> countBits(int n) {
final bits = List<int>.filled(n + 1, 0);
for (var i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
}
i & (i - 1) clears the lowest 1 bit, giving a smaller index with exactly one 1 bit fewer. Its stored count plus one is the count for i.
class Solution {
List<int> countBits(int n) {
final bits = List<int>.filled(n + 1, 0);
for (var i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}
Counting Bits in Scala
3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.
Array.tabulate(n + 1) fills each slot from a function of its index. For every i, a while loop adds the last bit x & 1 and shifts it off with x >>>= 1 until x is 0, one step per binary digit.
object Solution {
def countBits(n: Int): Array[Int] = Array.tabulate(n + 1) { i =>
var x = i
var ones = 0
while (x != 0) {
ones += x & 1
x >>>= 1
}
ones
}
}
new Array[Int](n + 1) starts every count at 0. Each entry is the count of i >> 1, stored earlier because it is smaller, plus the dropped bit i & 1. 1 to n is empty when n is 0.
object Solution {
def countBits(n: Int): Array[Int] = {
val bits = new Array[Int](n + 1)
for (i <- 1 to n) {
bits(i) = bits(i >> 1) + (i & 1)
}
bits
}
}
i & (i - 1) clears the lowest 1 bit, giving a smaller index with exactly one 1 bit fewer. Its stored count plus one is the count for i. A while loop keeps the hot path free of the range and closure a for creates.
object Solution {
def countBits(n: Int): Array[Int] = {
val bits = new Array[Int](n + 1)
var i = 1
while (i <= n) {
bits(i) = bits(i & (i - 1)) + 1
i += 1
}
bits
}
}
FAQ for Python
Can I just use bin(i).count("1")?
Yes, and it passes: [bin(i).count("1") for i in range(n + 1)] builds a string per number and counts its 1 characters. On Python 3.10 and later i.bit_count() does the same without the string and runs in C, so [i.bit_count() for i in range(n + 1)] is the shortest fast answer. The table versions are what the question is usually after, because they show the reuse.
Why is bits[i >> 1] already filled when the loop reads it?
Because i >> 1 is i // 2, which is smaller than i for every i of 1 or more, and the loop fills the list from left to right. Index 0 never needs filling: [0] * (n + 1) starts it at 0, which is the right count.
What does i & (i - 1) do?
Subtracting 1 flips the lowest 1 bit to 0 and every 0 below it to 1, so the AND keeps all higher bits and clears that lowest one. 12 is 0b1100, 11 is 0b1011, and 12 & 11 is 0b1000, which is 8. Repeating it until the number is 0 counts the 1 bits in as many steps as there are 1 bits.
Does the bit loop work for negative numbers?
No. Python integers have no fixed width, so -1 >> 1 is still -1 and while x: never ends. The constraints keep every number non-negative. For a 32-bit view of a negative value, mask it first: x = i & 0xFFFFFFFF turns -1 into 4294967295, which has 32 ones.
How much memory do these solutions use?
The answer list holds n + 1 integers, and none of the three needs anything beyond it and a few counters. The table versions use the answer itself as the table, which is why their extra space is O(1).
FAQ for JavaScript
Does JavaScript have a built-in popcount?
No. Math.clz32 counts leading zeros, not ones. The usual one-liner goes through a string: i.toString(2).split('1').length - 1 counts the 1 characters, which works but allocates a string and an array per number. The table versions avoid both.
Why i >> 1 and not i / 2?
i / 2 is a floating-point division, so 5 / 2 is 2.5 and bits[2.5] is undefined, which turns every later sum into NaN. i >> 1 drops the fraction because it works on integers. Math.floor(i / 2) gives the same result for non-negative numbers.
Do the bitwise operators work for numbers above 2^31?
Not as you might expect. >>, & and | first convert their operands to 32-bit signed integers, so 2 ** 31 >> 1 is -1073741824. The constraints stay far below that. For larger values use >>> (unsigned, up to 2^32 - 1) or BigInt, where 5n >> 1n is 2n.
Can I return a Uint8Array to save memory?
Not as the answer. A typed array is not a plain array, and JSON.stringify(new Uint8Array([0, 1])) gives {"0":0,"1":1}, an object. You can fill a Uint8Array (every count up to 10,000 fits in a byte) and return Array.from(bits) at the end.
What happens if I leave out fill(0)?
new Array(n + 1) creates empty slots, and reading one gives undefined. The table versions then compute bits[1] as undefined + 1, which is NaN, and every later entry is built from a NaN, so the whole answer turns into NaN (printed as null in JSON). fill(0) makes bits[0] a real 0 before the loop starts.
FAQ for TypeScript
Why annotate the empty array as number[]?
Without it, const result = [] starts as an evolving any[] and the compiler only settles its type from later pushes; with noImplicitAny on it can complain. const result: number[] = [] states the intent and makes a mistaken result.push("1") a compile error.
Can I return a Uint8Array instead of number[]?
The compiler rejects it: a Uint8Array is not assignable to number[] because it lacks methods such as push. It would also serialise to JSON as an object, not an array. Fill a typed array if you like and return Array.from(bits).
Is there a popcount function in TypeScript?
No, TypeScript adds no runtime library, and JavaScript has none either. i.toString(2).split("1").length - 1 counts the 1 characters, and the table versions are the fast way to get every count up to n.
Why does bits[i >> 1] type as number and not number | undefined?
Array indexing returns the element type by default. With the noUncheckedIndexedAccess option it becomes number | undefined and the addition needs a ! or a default. Here the index is always smaller than i, so the entry exists.
Do the bitwise operators handle large numbers?
They convert their operands to 32-bit signed integers, so values from 2^31 upward come out negative: 2 ** 31 >> 1 is -1073741824. The constraints stay well below that; for bigger inputs use >>> or bigint values.
FAQ for Java
Can I use Integer.bitCount instead?
Yes: for (int i = 0; i <= n; i++) result[i] = Integer.bitCount(i); passes, and the JIT turns Integer.bitCount into a single POPCNT instruction on most CPUs, so it is effectively O(n). The table versions show how to get there without a library call, which is the usual point of the question.
What is the difference between >> and >>> here?
>> copies the sign bit in from the left, >>> shifts in zeros. For non-negative numbers they agree. For a negative one, x >>= 1 never reaches 0 (-1 >> 1 is -1), so a bit loop would spin forever, while -1 >>> 1 is 2147483647 and the loop ends after 32 steps.
Why return int[] rather than List<Integer>?
An int[] stores the counts directly, starts zeroed and needs no boxing. A List<Integer> would wrap each count in an Integer object; counts this small come from the Integer cache, but the list still holds a reference per entry and every read unboxes.
Why does the table loop start at 1?
Index 0 already holds the right answer, 0, because Java zero-initialises arrays. Starting at 1 also keeps i - 1 from being -1 in the lowest-bit version.
Could this be written with streams?
IntStream.rangeClosed(0, n).map(Integer::bitCount).toArray() is a one-line version and fine for this size. A stream cannot read the entries it is producing, though, so the table versions stay as plain loops.
FAQ for Go
Is bits[i>>1] + i&1 parsed correctly without parentheses?
Yes. In Go, & binds tighter than + (it sits with * and << in the multiplication tier), so the expression reads as bits[i>>1] + (i & 1). That is the opposite of C, Java and JavaScript, where & binds looser than + and the parentheses are required. Writing them anyway costs nothing, and gofmt keeps them.
Does the standard library count bits for me?
math/bits has bits.OnesCount(x uint) int, which compiles to a POPCNT instruction where the CPU has one. It takes an unsigned value, so the loop body is result[i] = bits.OnesCount(uint(i)). Name the slice something other than bits in that version, or the package name is shadowed.
What happens with a negative number in the bit loop?
Go shifts a signed int arithmetically, so -1 >> 1 stays -1. The x > 0 condition stops the loop at once and reports 0 ones, which is wrong for a negative value but at least finite; x != 0 would spin forever. Convert to uint first if you need the bits of a negative number.
Why make([]int, n+1) instead of appending?
The table versions write bits[i] by index and read earlier entries, so the slice must already have length n+1. make allocates it once, zeroed. Appending to make([]int, 0, n+1) works for the bit loop too, as long as you index only what you have appended.
FAQ for C#
Is there a built-in way to count set bits in C#?
System.Numerics.BitOperations.PopCount(uint) has been there since .NET Core 3.0, and .NET 7 added int.PopCount(int) through generic math. Both compile to a POPCNT instruction where the CPU has one: result[i] = int.PopCount(i); passes in effectively O(n).
Why are the parentheses around i & 1 needed?
In C#, + binds tighter than &, so bits[i >> 1] + i & 1 means (bits[i >> 1] + i) & 1, which is 0 or 1 and wrong for most entries. The parentheses make the addition use the last bit.
What does >> do to a negative int?
It is an arithmetic shift: the sign bit is copied in, so -1 >> 1 stays -1 and a while (x != 0) bit loop never ends. C# 11 added >>>, which shifts in zeros, so -1 >>> 1 is int.MaxValue. The constraints keep every number non-negative.
Could LINQ build the array in one line?
Enumerable.Range(0, n + 1).Select(int.PopCount).ToArray() does it. LINQ cannot read the array it is still building, though, so the table versions need the plain for loop.
FAQ for C++
Should I use std::popcount or __builtin_popcount?
std::popcount from <bit> is standard C++20 and this lane compiles with -std=c++20; it only accepts unsigned types, so write popcount(unsigned(i)). __builtin_popcount is the GCC and Clang extension that came first. Both become a POPCNT instruction when the target allows it, and either passes every case.
Why are the parentheses around i & 1 needed?
In C++, + binds tighter than &, so bits[i >> 1] + i & 1 parses as (bits[i >> 1] + i) & 1. That compiles without an error and gives 0 or 1 for every entry; GCC warns with -Wparentheses if warnings are on.
Why shift an unsigned copy in the bit loop?
Shifting a negative signed integer right is arithmetic, so -1 >> 1 stays -1 and a while (x != 0) loop would never end. An unsigned copy always shifts in zeros. The constraints keep i non-negative, but the unsigned habit removes the trap.
Does returning the vector by value copy it?
No. Returning a local vector by name is either elided entirely or moved, so the caller receives the same buffer without copying the n + 1 elements.
Should I call reserve or construct with a size?
The table versions index bits[i] and read earlier entries, so the vector needs its full size up front: vector<int> bits(n + 1). reserve only allocates capacity; indexing past size() after it is undefined behaviour.
FAQ for C
Can I use __builtin_popcount instead?
On GCC and Clang, yes: result[i] = __builtin_popcount(i); passes and compiles to a POPCNT instruction when the target supports it (-mpopcnt or -march=native), otherwise to a short bit trick. It is a compiler extension, not standard C before C23, which adds stdc_count_ones in <stdbit.h>. The table versions are the portable answer.
Why copy i into an unsigned before shifting?
Right-shifting a negative signed int is implementation-defined in C; most compilers copy the sign bit in, so -1 >> 1 stays -1 and a while (x != 0) loop never ends. Shifting an unsigned always fills with zeros. The inputs here are non-negative, so it only matters if you reuse the loop elsewhere.
Why does bits[i >> 1] + (i & 1) need the parentheses?
In C, + has higher precedence than &. Without the parentheses, bits[i >> 1] + i & 1 parses as (bits[i >> 1] + i) & 1, which gives 0 or 1 for every entry. The same trap catches x & 1 == 0, which parses as x & (1 == 0).
Why calloc rather than malloc for the tables?
calloc returns memory set to zero, so bits[0] holds the right count without an assignment. malloc leaves the bytes undefined; with it you would write bits[0] = 0; before the loop. The first solution writes every entry, so plain malloc is enough there.
What does returnSize hold for this problem?
Always n + 1: one count for each number from 0 to n, so an n of 0 returns one int. The caller reads that many ints from the returned pointer and frees it.
FAQ for Kotlin
Is there a built-in bit count in Kotlin?
Yes: Int.countOneBits() (stable since Kotlin 1.6) returns the number of 1 bits, so IntArray(n + 1) { it.countOneBits() } passes. On the JVM it calls Integer.bitCount, which the JIT turns into a POPCNT instruction. The table versions show the reuse the problem is asking about.
Why does Kotlin write and, shr and ushr instead of &, >> and >>>?
Kotlin has no bitwise operator symbols; they are infix functions on Int: and, or, xor, inv(), shl, shr (sign-filling) and ushr (zero-filling). Being plain infix calls, they all bind looser than +, so bits[i shr 1] + (i and 1) needs the parentheses just as the C-style form would.
What is the difference between shr and ushr here?
shr copies the sign bit in from the left and ushr shifts in zeros. They agree for non-negative numbers. For a negative one, x shr 1 never reaches 0 (-1 shr 1 is -1), so the bit loop would spin forever, while -1 ushr 1 is 2147483647 and the loop ends after 32 steps.
Why return IntArray rather than List<Int>?
An IntArray is a primitive int[] on the JVM: no boxing, zero-initialised, and it is the type the harness expects. A List<Int> boxes each count; toIntArray() converts one if you built a list, at the cost of a copy.
FAQ for Rust
Can I use count_ones instead?
Yes: (0..=n).map(|i| i.count_ones() as i32).collect() passes. count_ones returns a u32 and compiles to a POPCNT instruction when the target has one (-C target-cpu=native), otherwise to a short bit trick. The table versions show the reuse the problem is after.
Why cast n to usize instead of indexing with i32?
Rust only indexes slices and vectors with usize. Converting n once with n as usize and looping over usize keeps the body free of casts; the other way round you would write bits[(i as usize) >> 1] on every line. The constraints keep n non-negative, so the cast is safe.
Why does (i & 1) need an as i32?
Rust never converts integer types implicitly. i is a usize in the table versions while bits holds i32, so i & 1 is a usize and must be cast before it can be added to bits[i >> 1]. In the first solution x is an i32 from the start, so no cast is needed.
Does the bit loop work for negative numbers?
Not as written: >> on a signed i32 is an arithmetic shift, so -1 >> 1 stays -1 and while x != 0 never ends. Shift an unsigned copy instead, let mut x = i as u32;, which fills with zeros and ends after 32 steps.
Why does the closure return ones without a semicolon?
A block in Rust evaluates to its last expression when that expression has no trailing semicolon. ones at the end of the closure is that value, so map yields one count per number and collect gathers them into the Vec<i32> the return type asks for.
FAQ for Swift
Is there a built-in bit count in Swift?
Yes: every fixed-width integer has nonzeroBitCount, so (0...n).map { $0.nonzeroBitCount } passes, with no import Foundation needed. It compiles to a POPCNT instruction where the CPU has one. The table versions show the reuse the problem is asking about.
Why stride instead of for i in 1...n?
A closed range needs its lower bound to be at most its upper bound, so 1...0 traps at run time with "Range requires lowerBound <= upperBound" when n is 0. stride(from: 1, through: n, by: 1) produces no values in that case. (0...n) in the first solution is fine because n is never negative.
Does Swift need the parentheses in bits[i >> 1] + (i & 1)?
Not for correctness: Swift puts & in the multiplication precedence group, above +, so bits[i >> 1] + i & 1 would already parse as intended. The parentheses keep the line readable for anyone used to C, where the same text means something else.
Does the bit loop work for negative numbers?
Not as written: >> on a signed Int is an arithmetic shift, so -1 >> 1 stays -1 and while x != 0 never ends. Shift an unsigned copy instead, var x = UInt(bitPattern: i), which fills with zeros and ends after 64 steps.
FAQ for PHP
Is there a built-in popcount in PHP?
Not in the core language. substr_count(decbin($i), '1') counts the 1 characters of the binary string and passes for this size; the GMP extension adds gmp_popcount when it is installed. The table versions need neither and run in one pass.
Why does $bits[$i >> 1] + ($i & 1) need the parentheses?
In PHP, as in C, + binds tighter than &. Without the parentheses the expression is ($bits[$i >> 1] + $i) & 1, which gives 0 or 1 for every entry. The same goes for $x & 1 == 0, which compares first.
Why append with $bits[] instead of filling an array first?
Appending to a PHP array in order creates keys 0, 1, 2 and so on, which is a list and encodes as a JSON array. array_fill(0, $n + 1, 0) followed by $bits[$i] = … works too; it just builds the zeros first.
Does the bit loop work for negative numbers?
No. PHP integers are signed 64-bit and >> is an arithmetic shift, so -1 >> 1 stays -1 and the loop never ends. Mask the value to the width you want first, for example $x = $i & 0xFFFFFFFF for a 32-bit view.
FAQ for Ruby
Can I just use i.to_s(2).count("1")?
Yes: (0..n).map { |i| i.to_s(2).count("1") } builds the binary string of each number and counts its 1 characters, and it passes for this size. i.digits(2).sum does the same with an array of binary digits instead of a string. The table versions show the reuse the problem is after.
Why does bits[i >> 1] + (i & 1) need the parentheses?
In Ruby, + binds tighter than &, as in C. Without the parentheses the line is (bits[i >> 1] + i) & 1, which gives 0 or 1 for every entry.
Is Array.new(n + 1, 0) safe here?
Yes, because Integers are immutable values: every slot holding the same 0 is harmless, and assigning bits[i] = … replaces the slot. The shared-default trap only bites with mutable defaults such as Array.new(3, []), where every slot is the same array; use the block form Array.new(3) { [] } for those.
Does the bit loop work for negative numbers?
No. Ruby Integers have no fixed width, so -1 >> 1 stays -1 and while x != 0 never ends. For a 32-bit view, mask the value first: x = i & 0xFFFFFFFF turns -1 into 4294967295, which has 32 ones.
FAQ for Dart
Is there a built-in bit count in Dart?
Not on int in the core library. i.toRadixString(2) gives the binary string, and '1'.allMatches(i.toRadixString(2)).length counts its 1s, which passes for this size. int.bitLength is the number of binary digits, not the number of 1 bits. The table versions avoid strings altogether.
Does Dart need the parentheses in bits[i >> 1] + (i & 1)?
Yes. Dart follows C here: + binds tighter than &, so bits[i >> 1] + i & 1 would parse as (bits[i >> 1] + i) & 1 and give 0 or 1 for every entry.
What is the difference between List.filled and List.generate?
List.filled(n + 1, 0) puts the same value in every slot, which is fine for an immutable int. List.generate(n + 1, f) calls f(i) for each index, which suits the first solution. Both return a fixed-length list by default; pass growable: true if you need to add to it later.
Does the bit loop work for negative numbers?
Not as written: on the VM int is a signed 64-bit value and >> is an arithmetic shift, so -1 >> 1 stays -1 and the loop never ends. Dart 2.14 added >>>, the zero-filling shift, and x >>>= 1 ends after 64 steps.
FAQ for Scala
Is there a built-in bit count in Scala?
Scala uses the JVM one: Array.tabulate(n + 1)(Integer.bitCount) passes, and the JIT turns Integer.bitCount into a POPCNT instruction on most CPUs. java.lang.Integer is visible without an import. The table versions show the reuse the problem is asking about.
Why does bits(i >> 1) + (i & 1) need the parentheses?
Scala sets operator precedence by the first character of the operator, and + ranks above &. Without the parentheses the line is (bits(i >> 1) + i) & 1, which gives 0 or 1 for every entry.
What is the difference between >> and >>> in Scala?
They are the JVM shifts: >> copies the sign bit in, >>> shifts in zeros. They agree for non-negative numbers. For a negative one x >>= 1 never reaches 0, while x >>>= 1 ends after 32 steps, which is why the bit loop uses >>>.
Why is the result an Array[Int] and not a List[Int]?
Array[Int] compiles to a primitive int[], zero-initialised and indexable in constant time, which the table versions need. An immutable List has linear-time indexing, so bits(i >> 1) on it would make the table quadratic; build a Vector or an Array instead.
Keep going
Missing Number13 / 40 · Math · EasyTry Counting Bits in Python (Counting Bits in Python), JavaScript (Counting Bits in JavaScript), TypeScript (Counting Bits in TypeScript), Go (Counting Bits in Go), C# (Counting Bits in C#), C++ (Counting Bits in C++), C (Counting Bits in C), Kotlin (Counting Bits in Kotlin), Rust (Counting Bits in Rust), Swift (Counting Bits in Swift), PHP (Counting Bits in PHP), Ruby (Counting Bits in Ruby), Dart (Counting Bits in Dart) or Scala (Counting Bits in Scala) instead.