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 these in an interview costs you the question

  • 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

resolving links…