skip to content

What do countOneBits, countLeadingZeroBits, and countTrailingZeroBits do on Int/Long, and what are typical uses?

level: seniorimportance: should knowfreq 30%

answer

  1. countOneBits = popcount (Hamming, cardinality)
  2. leadingZeros -> bit length & next power of two
  3. trailingZeros = index of lowest set bit
  4. takeHighest/LowestOneBit isolate one bit
  5. Zero input -> leading/trailing return full width (32/64)

basics

~10 s

They count bits in a number: countOneBits counts the 1s (population count), countLeadingZeroBits counts zeros before the first 1 from the left, and countTrailingZeroBits counts zeros after the last 1 from the right.

solid answer

~40 s

Kotlin's stdlib adds bit-introspection extension functions on Int and Long. countOneBits() returns the popcount (number of set bits) — useful for Hamming distance (a xor b).countOneBits() or cardinality of a bitset word. countLeadingZeroBits() counts high zero bits before the most-significant 1; it gives 32 (Int)/64 (Long) for zero and lets you compute the bit-length or next power of two. countTrailingZeroBits() counts low zero bits, equal to the index of the lowest set bit (useful to iterate set bits). There are also takeHighestOneBit()/takeLowestOneBit() returning just that single bit, and rotateLeft(n)/rotateRight(n). These compile to hardware instructions (POPCNT, LZCNT, TZCNT / Java's Integer.bitCount, numberOfLeadingZeros) so they're fast. All return Int counts.

code

kotlin · 6 lines
kotlin
println(0b1011.countOneBits())          // 3
println(1.countLeadingZeroBits())       // 31 (Int)
println(0b1000.countTrailingZeroBits()) // 3
println(0b1011.takeHighestOneBit())     // 8
println(0b1100.takeLowestOneBit())      // 4
println(0.countLeadingZeroBits())       // 32

go deeper

for a junior

Knows countOneBits counts set bits.

for a middle

Distinguishes leading vs trailing zero counts and gives a popcount use like Hamming distance.

for a senior

Uses trailing zeros to iterate set bits, knows takeOneBit/rotate, and the zero-input edge case.

for a principal

Reasons about intrinsics/perf, power-of-two/bitlength derivations, and where these beat data-structure alternatives.

## The introspection family Kotlin exposes per-bit query functions as extensions on `Int` and `Long` (and the unsigned types). They all **return an `Int` count**. - **`countOneBits()`** — the **population count** (popcount): how many bits are 1. `0b1011.countOneBits() == 3`. Maps to JVM `Integer.bitCount`. - **`countLeadingZeroBits()`** — number of 0 bits **above** the highest set bit (from the most-significant side). `1.countLeadingZeroBits() == 31` for an Int; `0.countLeadingZeroBits() == 32`. Maps to `Integer.numberOfLeadingZeros`. - **`countTrailingZeroBits()`** — number of 0 bits **below** the lowest set bit. `0b1000.countTrailingZeroBits() == 3`; `0` returns the full width (32/64). ## Companion single-bit helpers - **`takeHighestOneBit()`** — the value with only the highest set bit kept (the largest power of two <= input as a bit). `0b1011.takeHighestOneBit() == 0b1000`. - **`takeLowestOneBit()`** — only the lowest set bit. `0b1100.takeLowestOneBit() == 0b0100`. - **`rotateLeft(n)` / `rotateRight(n)`** — circular shifts where bits shifted off one end re-enter the other (unlike shl/shr which drop them). ## Why they exist / typical uses ```kotlin // Hamming distance between two ints fun hamming(a: Int, b: Int) = (a xor b).countOneBits() // Bit length (position of highest set bit + 1) fun bitLength(x: Int) = Int.SIZE_BITS - x.countLeadingZeroBits() // 32 - lz // Iterate set-bit indices var m = 0b101100 while (m != 0) { val idx = m.countTrailingZeroBits() // lowest set bit index println(idx) m = m and (m - 1) // clear lowest set bit } ``` Other uses: checking power-of-two (`x.countOneBits() == 1`), computing the next power of two, fast cardinality of bitset words, and hashing. ## Performance These are intrinsified to dedicated CPU instructions (POPCNT/LZCNT/TZCNT) via the corresponding `java.lang.Integer`/`Long` static methods, so they are constant-time, far faster than a manual loop. ## Summary countOneBits = how many 1s; countLeadingZeroBits / countTrailingZeroBits = run of 0s at the top / bottom; plus take*OneBit and rotate* round out the bit-introspection toolkit.

  • How do you test if an Int is a power of two using these functions?
    x > 0 && x.countOneBits() == 1 — a power of two has exactly one set bit. Equivalently x and (x - 1) == 0 for x > 0.
  • What does countLeadingZeroBits return for 0, and why does that matter?
    It returns the full width: 32 for Int, 64 for Long. So bitLength of 0 computes to 0, which is correct, but you must guard if you derive a shift count from it.

countLeadingZeroBits is like counting empty parking spots before the first parked car when scanning the lot from the entrance.

  • Saying countOneBits counts zeros or vice versa
  • Claiming these are slow software loops
  • Not knowing zero yields full-width leading/trailing counts
  • Confusing takeHighestOneBit (a value) with countLeadingZeroBits (a count)
  • Thinking rotateLeft drops bits like shl

context