Project Nayuki


Some bit-twiddling functions explained

Introduction

Using clever bitwise arithmetic, it’s possible to implement some useful arithmetic functions in a short amount of code without using expensive loops or branches (if-statements). Here I will give some bit-twiddling functions expressed in the Java programming language and give proofs to justify their correctness.

For those who are unfamiliar with the specifics of Java but know another programming language well:

Absolute value

Naive version:

int abs(int x) {
    if (x >= 0)
        return x;
    else
        return -x;
}

Bit-twiddling version:

int abs(int x) {
    int y = x >> 31;
    return (x + y) ^ y;
}

How this implementation works is as follows: y is the sign bit of x replicated to all 32 bits. If x >= 0, then y == 0, and (x + 0) ^ 0 == x. Otherwise x < 0, which means bit #31 of x is 1, so y == 0xFFFFFFFF. By definition since x has the type int, we have ~x == (x ^ 0xFFFFFFFF). By the definition of two’s complement arithmetic, -x == (~x) + 1 == ~(x - 1). With y == -1, we have (x + y) ^ y == ~(x + (-1)) == ~(x - 1) == -x.

The line of code containing return can be written equivalently as: return (x ^ y) - y;. The proof is left as an exercise to the reader.

Take note of one caveat: the most negative number, Integer.MIN_VALUE = −231 = −2147483648, does not have a positive counterpart. But this implementation gives abs(Integer.MIN_VALUE) == Integer.MIN_VALUE instead of throwing an exception, much like Math.abs(int).

Sign function

Naive version:

int sign(int x) {
    if (x > 0)
        return +1;
    else if (x < 0)
        return -1;
    else
        return 0;
}

Bit-twiddling version:

int sign(int x) {
    return (x >> 31) | ((-x) >>> 31);
}

To show why this implementation of the sign function is correct, consider the three cases:

Power-of-2 test

Naive version:

boolean isPowerOf2(int x) {
    for (int i = 0; i <= 30; i++) {
        if ((1 << i) == x)
            return true;
    }
    return false;
}

Bit-twiddling version:

boolean isPowerOf2(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

This function returns true if x == 1, 2, 4, 8, 16, ..., 1073741824 but false otherwise. To start, the condition x > 0 excludes numbers that cannot possibly be a positive integral power of 2. Now consider two cases:

Set nonzero to all ones

Naive version:

int isNonzero(int x) {
    if (x == 0)
        return 0x00000000;
    else
        return 0xFFFFFFFF;
}

Bit-twiddling version:

int isNonzero(int x) {
    return (x | (-x)) >> 31;
}

Proof of correctness:

This simple function serves as a useful building block for expressing conditional statements that can be evaluated in constant time regardless of input values. Constant-time execution is important in the implementation of cryptographic primitives (e.g. ciphers, bigint arithmetic) because variations in timing could disclose information about secret inputs (e.g. keys, messages). I applied tricks similar to this isNonzero() function in my Bitcoin cryptography library, especially in the implementation of ECDSA such as in Int256Math.java.

More info