Bit Hacks

Author: Jacob Park

Bit Array

In [1]:
package bit_hacks.bit_array;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.util.Arrays;

public final class BitArray {
    
    private final long[] data;
    private long bitCount;

    public BitArray(long numBits) {
        this(new long[numWords(numBits)]);
    }

    private BitArray(long[] data) {
        this.data = data;
        long bitCount = 0;
        for (long word : data) {
            bitCount += Long.bitCount(word);
        }
        this.bitCount = bitCount;
    }

    private static int numWords(long numBits) {
        if (numBits <= 0) {
            final String error = String.format(
                "numBits must be positive, but got %d", numBits);
            throw new IllegalArgumentException(error);
        }
        final long numWords = (long) Math.ceil(numBits / 64D);
        if (numWords > Integer.MAX_VALUE) {
            final String error = String.format(
                "Cannot allocate enough space for %d bits", numBits);
            throw new IllegalArgumentException(error);
        }
        return (int) numWords;
    }

    public boolean get(long index) {
        final int arrayIndex = (int)(index >>> 6);
        final long bitMask = 1L << index;
        return (data[arrayIndex] & bitMask) != 0;
    }

    public boolean set(long index) {
        final int arrayIndex = (int)(index >>> 6);
        final long bitMask = 1L << index;
        if ((data[arrayIndex] & bitMask) == 0) {
            data[arrayIndex] |= bitMask;
            bitCount++;
            return true;
        }
        return false;
    }

    public boolean clear(long index) {
        final int arrayIndex = (int)(index >>> 6);
        final long bitMask = 1L << index;
        if ((data[arrayIndex] & bitMask) != 0) {
            data[arrayIndex] &= ~bitMask;
            bitCount--;
            return true;
        }
        return false;
    }

    public long bitSize() {
        return (long) data.length * Long.SIZE;
    }

    public long bitCount() {
        return bitCount;
    }

    public void putAll(BitArray array) {
        if (data.length != array.data.length) {
            final String error = String.format(
                    "BitArrays must be of equal length (%d != %d)",
                    data.length,
                    array.data.length);
            throw new IllegalArgumentException(error);
        }
        long bitCount = 0;
        for (int i = 0; i < data.length; i++) {
            data[i] |= array.data[i];
            bitCount += Long.bitCount(data[i]);
        }
        this.bitCount = bitCount;
    }
    
    public void writeTo(DataOutputStream out) throws IOException {
        out.writeInt(data.length);
        for (long datum : data) {
            out.writeLong(datum);
        }
    }

    public static BitArray readFrom(DataInputStream in) throws IOException {
        final int numWords = in.readInt();
        long[] data = new long[numWords];
        for (int i = 0; i < numWords; i++) {
            data[i] = in.readLong();
        }
        return new BitArray(data);
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (other == null || getClass() != other.getClass()) {
            return false;
        }
        final BitArray that = (BitArray) other;
        return Arrays.equals(data, that.data);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(data);
    }
    
}
Out[1]:
bit_hacks.bit_array.BitArray

Standard Library API

See Link.
See Link.

Bit Count

  • Returns the number of one-bits in the two's complement binary representation of the specified value.
In [2]:
package bit_hacks.bit_count;

System.out.println(Integer.bitCount(3));
System.out.println(Long.bitCount(3));

2
2
Out[2]:
null

Highest One Bit

  • Returns a value with at most a single one-bit, in the position of the highest-order ("leftmost") one-bit in the specified value.
In [3]:
package bit_hacks.highest_one_bit;

System.out.println(Integer.highestOneBit(3));
System.out.println(Long.highestOneBit(3));

2
2
Out[3]:
null

Lowest One Bit

  • Returns a value with at most a single one-bit, in the position of the lowest-order ("rightmost") one-bit in the specified value.
In [4]:
package bit_hacks.lowest_one_bit;

System.out.println(Integer.lowestOneBit(3));
System.out.println(Long.lowestOneBit(3));

1
1
Out[4]:
null

Number of Leading Zeros

  • Returns the number of zero bits preceding the highest-order ("leftmost") one-bit in the two's complement binary representation of the specified value.
In [5]:
package bit_hacks.number_of_leading_zeros;

System.out.println(Integer.numberOfLeadingZeros(3));
System.out.println(Long.numberOfLeadingZeros(3));

30
62
Out[5]:
null

Number of Trailing Zeros

  • Returns the number of zero bits following the lowest-order ("rightmost") one-bit in the two's complement binary representation of the specified value.
In [6]:
package bit_hacks.number_of_trailing_zeros;

System.out.println(Integer.numberOfTrailingZeros(3));
System.out.println(Long.numberOfTrailingZeros(3));

0
0
Out[6]:
null

Reverse

  • Returns the value obtained by reversing the order of the bits in the two's complement binary representation of the specified value.
In [7]:
package bit_hacks.reverse;

System.out.println(Integer.reverse(3));
System.out.println(Long.reverse(3));

-1073741824
-4611686018427387904
Out[7]:
null

Reverse Bytes

  • Returns the value obtained by reversing the order of the bytes in the two's complement representation of the specified value.
In [8]:
package bit_hacks.reverse_bytes;

System.out.println(Integer.reverseBytes(3));
System.out.println(Long.reverseBytes(3));

50331648
216172782113783808
Out[8]:
null

Rotate Left

  • Returns the value obtained by rotating the two's complement binary representation of the specified value left by the specified number of bits.
In [9]:
package bit_hacks.rotate_left;

System.out.println(Integer.rotateLeft(3, 2));
System.out.println(Long.rotateLeft(3, 2));

12
12
Out[9]:
null

Rotate Right

  • Returns the value obtained by rotating the two's complement binary representation of the specified value right by the specified number of bits.
In [10]:
package bit_hacks.rotate_right;

System.out.println(Integer.rotateRight(3, 2));
System.out.println(Long.rotateRight(3, 2));

-1073741824
-4611686018427387904
Out[10]:
null

Miscellaneous Hacks

Signed/Unsigned Multiplication and Division by 2

In [11]:
package bit_hacks.miscellaneous_hack_1;

System.out.println(1 * 4 == 1 << 2);
System.out.println(4 / 2 == 4 >> 1);
System.out.println(-1 * 4 == -1 << 2);
System.out.println(-4 / 2 == -4 >> 1);

true
true
true
true
Out[11]:
null

Unsigned Modulo Power of 2

In [12]:
package bit_hacks.miscellaneous_hack_2;

System.out.println((1337 % 32) == (1337 & (32 - 1)));

true
Out[12]:
null

Signed/Unsigned At Least One Zero

In [13]:
package bit_hacks.miscellaneous_hack_3;

final int A = 0;
final int B = 0;
System.out.println((A & B) == 0);
final int C = 0;
final int D = 2;
System.out.println((C & D) == 0);
final int E = 2;
final int F = 2;
System.out.println((E & F) == 0);

true
true
false
Out[13]:
null

Signed/Unsigned Both Zero

In [14]:
package bit_hacks.miscellaneous_hack_4;

final int A = 0;
final int B = 0;
System.out.println((A | B) == 0);
final int C = 0;
final int D = 2;
System.out.println((C | D) == 0);
final int E = 2;
final int F = 2;
System.out.println((E | F) == 0);

true
false
false
Out[14]:
null

Unsigned Floor Average of 2 Numbers

In [15]:
package bit_hacks.miscellaneous_hack_5;

final int A = 1;
final int B = 2;
System.out.println((int) Math.floor((A + B) / 2.0));
System.out.println((A & B) + ((A ^ B) >> 1));

1
1
Out[15]:
null

Unsigned Ceil Average of 2 Numbers

In [16]:
package bit_hacks.miscellaneous_hack_6;

final int A = 1;
final int B = 2;
System.out.println((int) Math.ceil((A + B) / 2.0));
System.out.println((A | B) - ((A ^ B) >> 1));

2
2
Out[16]:
null

Signed/Unsigned Toggling Between A or B

In [17]:
package bit_hacks.miscellaneous_hack_7;

final int A = 1;
final int B = 2;
final int T = A ^ B;
System.out.println(A ^ T);
System.out.println((A ^ T) ^ T);
System.out.println(((A ^ T) ^ T) ^ T);

2
1
2
Out[17]:
null

Signed/Unsigned Next/Previous Even/Odd Value

In [18]:
package bit_hacks.miscellaneous_hack_8;

final int X = 1;
System.out.println(String.format("Next Even: %d", (X | 1) + 1));
System.out.println(String.format("Previous Even: %d", (X - 1) & ~1));
System.out.println(String.format("Next Odd: %d", (X + 1) | 1));
System.out.println(String.format("Previous Odd: %d", (X & ~1) - 1));

Next Even: 2
Previous Even: 0
Next Odd: 3
Previous Odd: -1
Out[18]:
null