What bit operations does BigInteger provide, and what is the performance cost model you should keep in mind?

## BigInteger as an infinite two's-complement bit string For bit operations, `BigInteger` behaves as if the number were written in **two's complement** (the standard binary encoding of signed integers) and then **sign-extended infinitely** to the left — a positive number has infinitely many leading 0 bits, a negative number infinitely many leading 1 bits. This makes the bitwise operators well-defined for negatives too. ## The bitwise / bit-twiddling API **Logical combinators** (each takes another BigInteger, returns a new one): - `and`, `or`, `xor`, `not`, `andNot(x)` (= `this AND (NOT x)`). **Shifts:** - `shiftLeft(n)` — moves bits left by n positions = multiply by 2^n. - `shiftRight(n)` — moves bits right by n = **arithmetic** (sign-preserving) divide by 2^n, rounding toward negative infinity for negatives. **Single-bit access** (bit 0 is least significant): - `testBit(i)` — is bit i set? `setBit(i)`, `clearBit(i)`, `flipBit(i)` — return a copy with that bit changed. **Queries:** - `bitLength()` — number of bits in the minimal two's-complement representation *excluding* the sign bit (so the count of significant bits). - `bitCount()` — number of bits that **differ from the sign bit** (population count of magnitude bits). - `getLowestSetBit()` — index of the rightmost set bit, or -1 for zero. ## The cost model — why this matters Internally a `BigInteger` stores its magnitude as an array of 32-bit **words** (`int[]`). A number with `n` significant bits uses about `n/32` words. From that you can reason about cost: - **Bitwise ops and shifts:** time and fresh allocation proportional to the word count, O(n/32). Cheap per element but it still walks the whole array and **allocates a new object** every call (immutability). - **add / subtract:** linear in the larger operand's word count. - **multiply:** the JDK uses schoolbook O(n^2) for small operands, then **Karatsuba** (~O(n^1.585)) and **Toom-Cook** for large ones — important when numbers are thousands of bits. - **divide / mod:** also super-linear; the most expensive common ops. The two practical takeaways: 1. **Allocation pressure.** Because every operation produces a new object, a tight loop doing millions of BigInteger ops generates millions of short-lived objects, hammering the garbage collector. This is the dominant reason BigInteger is slow in hot paths. 2. **Use primitives when you can.** If the value provably fits in 64 bits, `long` bit operations are vastly faster (registers, no allocation). Reach for BigInteger's bit API only when the value genuinely exceeds 64 bits — e.g. large bitsets-as-numbers, crypto, or arbitrary-width masks. ## A worked feel ```java BigInteger n = BigInteger.ONE.shiftLeft(1000); // 2^1000, a ~1000-bit number int bits = n.bitLength(); // 1001 int ones = n.bitCount(); // 1 (only one bit set) boolean b = n.testBit(1000); // true BigInteger half = n.shiftRight(1); // 2^999 ``` Note `shiftLeft(1000)` is the idiomatic, cheap way to build 2^1000 — far better than `BigInteger.TWO.pow(1000)` semantically and competitive in cost. ## Pitfalls - Forgetting results are new objects (immutability) — capture them. - Assuming `bitCount()` counts set bits even for negatives — it counts bits *differing from the sign bit*, so for a negative number it counts zero-bits in the magnitude region. - Using BigInteger bit ops where a `long` or `java.util.BitSet` would do — both are much faster for bounded sizes.