位运算技巧整理

1
/**
2
 * ### 1. 计算整数的符号 ###
3
 * 计算整数的符号。
4
 * @param v 待计算的整数。
5
 * @return -1 (负数), 0 (零), 或 +1 (正数)。
6
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign">Original C version</a>
7
 */
8
public static int getSign(int v) {
9
    return (v >> 31) | (-v >>> 31);
10
}

1
@Test
2
@DisplayName("1. 计算整数的符号")
3
void testGetSign() {
4
    assertEquals(1, BitHacks.getSign(123));
5
    assertEquals(-1, BitHacks.getSign(-456));
6
    assertEquals(0, BitHacks.getSign(0));
7
    assertEquals(1, BitHacks.getSign(Integer.MAX_VALUE));
8
    assertEquals(-1, BitHacks.getSign(Integer.MIN_VALUE));
9
}

Integer.signum(int v)

1
/**
2
 * ### 2. 检测两个整数的符号是否相反 ###
3
 * @param x 第一个整数。
4
 * @param y 第二个整数。
5
 * @return 如果符号相反则返回 true。
6
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#DetectOppositeSigns">Original C version</a>
7
 */
8
public static boolean haveOppositeSigns(int x, int y) {
9
    return (x ^ y) < 0;
10
}

1
@Test
2
@DisplayName("2. 检测两个整数的符号是否相反")
3
void testHaveOppositeSigns() {
4
    assertTrue(BitHacks.haveOppositeSigns(100, -50));
5
    assertTrue(BitHacks.haveOppositeSigns(-1, 1));
6
    assertFalse(BitHacks.haveOppositeSigns(10, 20));
7
    assertFalse(BitHacks.haveOppositeSigns(-10, -20));
8
    assertFalse(BitHacks.haveOppositeSigns(0, 100));
9
    assertFalse(BitHacks.haveOppositeSigns(0, -100));
10
    assertFalse(BitHacks.haveOppositeSigns(0, 0));
11
}

1
/**
2
 * ### 3. 无分支计算整数绝对值 ###
3
 * @param v 待计算的整数。
4
 * @return v 的绝对值。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs">Original C version</a>
6
 */
7
public static int absWithoutBranch(int v) {
8
    int mask = v >> 31;
9
    return (v + mask) ^ mask;
10
}

1
@Test
2
@DisplayName("3. 无分支计算整数绝对值")
3
void testAbsWithoutBranch() {
4
    assertEquals(123, BitHacks.absWithoutBranch(123));
5
    assertEquals(123, BitHacks.absWithoutBranch(-123));
6
    assertEquals(0, BitHacks.absWithoutBranch(0));
7
    assertEquals(Integer.MAX_VALUE, BitHacks.absWithoutBranch(Integer.MAX_VALUE));
8
    // Note: abs(Integer.MIN_VALUE) is still Integer.MIN_VALUE due to overflow
9
    assertEquals(Integer.MIN_VALUE, BitHacks.absWithoutBranch(Integer.MIN_VALUE));
10
}

Math.abs(int v)

1
/**
2
 * ### 4. 无分支计算两个整数的最小值 ###
3
 * @param x 第一个整数。
4
 * @param y 第二个整数。
5
 * @return x 和 y 中的较小值。
6
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax">Original C version</a>
7
 */
8
public static int minWithoutBranch(int x, int y) {
9
    return y ^ ((x ^ y) & ((x - y) >> 31));
10
}
11

12
public static int maxWithoutBranch(int x, int y) {
13
    return x ^ ((x ^ y) & ((x - y) >> 31));
14
}

1
@Test
2
@DisplayName("4. 无分支计算最小值和最大值")
3
void testMinMaxWithoutBranch() {
4
    assertEquals(5, BitHacks.minWithoutBranch(5, 10));
5
    assertEquals(5, BitHacks.minWithoutBranch(10, 5));
6
    assertEquals(-10, BitHacks.minWithoutBranch(-5, -10));
7
    assertEquals(-5, BitHacks.maxWithoutBranch(-5, -10));
8
    assertEquals(10, BitHacks.maxWithoutBranch(5, 10));
9
    assertEquals(10, BitHacks.maxWithoutBranch(10, 5));
10
}

1
/**
2
 * ### 5. 判断一个整数是否是2的幂 ###
3
 * @param v 待检查的正整数。
4
 * @return 如果是2的幂则返回 true。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2">Original C version</a>
6
 */
7
public static boolean isPowerOfTwo(int v) {
8
    return (v > 0) && ((v & (v - 1)) == 0);
9
}

1
@Test
2
@DisplayName("5. 判断一个整数是否是2的幂")
3
void testIsPowerOfTwo() {
4
    assertTrue(BitHacks.isPowerOfTwo(1));
5
    assertTrue(BitHacks.isPowerOfTwo(2));
6
    assertTrue(BitHacks.isPowerOfTwo(16));
7
    assertTrue(BitHacks.isPowerOfTwo(1024));
8
    assertTrue(BitHacks.isPowerOfTwo(1 << 30));
9
    assertFalse(BitHacks.isPowerOfTwo(0));
10
    assertFalse(BitHacks.isPowerOfTwo(3));
11
    assertFalse(BitHacks.isPowerOfTwo(15));
12
    assertFalse(BitHacks.isPowerOfTwo(-4));
13
}

(v > 0) && (Integer.bitCount(v) == 1)

1
/**
2
 * ### 6. 符号扩展 ###
3
 * 从可变位宽进行符号扩展。
4
 * @param x 包含b位有符号数的整数。
5
 * @param b x中实际使用的位数 (1-32)。
6
 * @return 符号扩展后的整数。
7
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtend">Original C version</a>
8
 */
9
public static int signExtendFrom(int x, int b) {
10
    if (b <= 0 || b > 32)
11
        throw new IllegalArgumentException("Bit width b must be between 1 and 32.");
12
    if (b == 32) return x;
13
    int mask = 1 << (b - 1);
14
    int value = x & ((1 << b) - 1);
15
    return (value ^ mask) - mask;
16
}

1
@Test
2
@DisplayName("6, 7, 8. 符号扩展")
3
void testSignExtendFrom() {
4
    // 5-bit number 10 (01010) -> 10
5
    assertEquals(10, BitHacks.signExtendFrom(0b01010, 5));
6
    // 5-bit number -6 (11010) -> -6
7
    assertEquals(-6, BitHacks.signExtendFrom(0b11010, 5));
8
    // 5-bit number -1 (11111) -> -1
9
    assertEquals(-1, BitHacks.signExtendFrom(0b11111, 5));
10
    // 8-bit number 127 -> 127
11
    assertEquals(127, BitHacks.signExtendFrom(127, 8));
12
    // 8-bit number -128 -> -128
13
    assertEquals(-128, BitHacks.signExtendFrom(0b10000000, 8));
14
    // 32-bit number
15
    assertEquals(Integer.MIN_VALUE, BitHacks.signExtendFrom(Integer.MIN_VALUE, 32));
16
}

1
/**
2
 * ### 9. 无分支地条件性设置或清除位 ###
3
 * 等效于: if (flag) w |= m; else w &= ~m;
4
 * @param w 待修改的字。
5
 * @param m 掩码。
6
 * @param flag 条件标志。
7
 * @return 修改后的字。
8
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching">Original C version</a>
9
 */
10
public static int conditionalSetClear(int w, int m, boolean flag) {
11
    int f = flag ? -1 : 0;
12
    return w ^ ((f ^ w) & m);
13
}

1
@Test
2
@DisplayName("9. 无分支地条件性设置或清除位")
3
void testConditionalSetClear() {
4
    int w = 0b10101010;
5
    int m = 0b00001111;
6
    // if (true) w |= m -> 10101111
7
    assertEquals(0b10101111, BitHacks.conditionalSetClear(w, m, true));
8
    // if (false) w &= ~m -> 10100000
9
    assertEquals(0b10100000, BitHacks.conditionalSetClear(w, m, false));
10
}

1
/**
2
 * ### 10. 无分支地条件性取反一个值 ###
3
 * 等效于: fNegate ? -v : v;
4
 * @param v 待取反的值。
5
 * @param fNegate 是否取反的标志。
6
 * @return 结果。
7
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#ConditionalNegate">Original C version</a>
8
 */
9
public static int conditionalNegate(int v, boolean fNegate) {
10
    int f = fNegate ? -1 : 0;
11
    return (v ^ f) - f;
12
}

1
@Test
2
@DisplayName("10. 无分支地条件性取反一个值")
3
void testConditionalNegate() {
4
    assertEquals(-123, BitHacks.conditionalNegate(123, true));
5
    assertEquals(123, BitHacks.conditionalNegate(123, false));
6
    assertEquals(123, BitHacks.conditionalNegate(-123, true));
7
    assertEquals(-123, BitHacks.conditionalNegate(-123, false));
8
}

1
/**
2
 * ### 11. 根据掩码合并两个值的位 ###
3
 * 等效于: (a & ~mask) | (b & mask);
4
 * @param a 当掩码位为0时取此值。
5
 * @param b 当掩码位为1时取此值。
6
 * @param mask 掩码。
7
 * @return 合并后的值。
8
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge">Original C version</a>
9
 */
10
public static int mergeBits(int a, int b, int mask) {
11
    return a ^ ((a ^ b) & mask);
12
}

1
@Test
2
@DisplayName("11. 根据掩码合并两个值的位")
3
void testMergeBits() {
4
    int a = 0b11110000;
5
    int b = 0b00001111;
6
    int mask = 0b00110011;
7
    // expected: (a & ~mask) | (b & mask) = (11000000) | (00000011) = 11000011
8
    assertEquals(0b11000011, BitHacks.mergeBits(a, b, mask));
9
}

1
/**
2
 * ### 14. 计算置位数 (Brian Kernighan's way) ###
3
 * 循环次数等于置位(1)的数量。
4
 * @param v 待计算的整数。
5
 * @return 置位(1)的数量。
6
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan">Original C version</a>
7
 */
8
public static int countSetBits(int v) {
9
    int c = 0;
10
    while (v != 0) {
11
        v &= (v - 1);
12
        c++;
13
    }
14
    return c;
15
}

1
@Test
2
@DisplayName("14. 计算置位数 (Kernighan)")
3
void testCountSetBits() {
4
    // 测试0的置位数（二进制表示全0）
5
    assertEquals(0, BitHacks.countSetBits(0));
6

7
    // 测试1的置位数（二进制0001）
8
    assertEquals(1, BitHacks.countSetBits(1));
9

10
    // 测试8的置位数（二进制1000）
11
    assertEquals(1, BitHacks.countSetBits(8));
12

13
    // 测试9的置位数（二进制1001）
14
    assertEquals(2, BitHacks.countSetBits(9));
15

16
    // 测试Integer.MAX_VALUE的置位数（二进制011...1，共31个1）
17
    assertEquals(31, BitHacks.countSetBits(Integer.MAX_VALUE));
18

19
    // 测试-1的置位数（二进制全1，共32个1）
20
    assertEquals(32, BitHacks.countSetBits(-1));
21
}

Integer.bitCount(v)

1
/**
2
 * ### 16. 并行计算置位数 ###
3
 * @param v 待计算的32位整数。
4
 * @return 置位(1)的数量。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel">Original C version</a>
6
 */
7
public static int countSetBitsParallel(int v) {
8
    v = v - ((v >>> 1) & 0x55555555);
9
    v = (v & 0x33333333) + ((v >>> 2) & 0x33333333);
10
    return (((v + (v >>> 4)) & 0x0F0F0F0F) * 0x01010101) >>> 24;
11
}

1
@Test
2
@DisplayName("16. 并行计算置位数")
3
void testCountSetBitsParallel() {
4
    assertEquals(0, BitHacks.countSetBitsParallel(0));
5
    assertEquals(1, BitHacks.countSetBitsParallel(1));
6
    assertEquals(8, BitHacks.countSetBitsParallel(0x11111111));
7
    assertEquals(31, BitHacks.countSetBitsParallel(Integer.MAX_VALUE));
8
    assertEquals(32, BitHacks.countSetBitsParallel(-1));
9
}

1
@HotSpotIntrinsicCandidate
2
public static int bitCount(int i) {
3
    // HD, Figure 5-2
4
    i = i - ((i >>> 1) & 0x55555555);
5
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
6
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
7
    i = i + (i >>> 8);
8
    i = i + (i >>> 16);
9
    return i & 0x3f;
10
}

1
/**
2
 * ### 23. 并行计算奇偶校验位 ###
3
 * @param v 待计算的32位整数。
4
 * @return 如果1的个数为奇数返回true, 否则返回false。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#ParityParallel">Original C version</a>
6
 */
7
public static boolean getParity(int v) {
8
    v ^= v >>> 16;
9
    v ^= v >>> 8;
10
    v ^= v >>> 4;
11
    v &= 0x0f;
12
    return ((0x6996 >>> v) & 1) != 0;
13
}

1
@Test
2
@DisplayName("23. 并行计算奇偶校验位")
3
void testGetParity() {
4
    assertTrue(BitHacks.getParity(7));  // 0111 -> 3 ones (odd)
5
    assertFalse(BitHacks.getParity(6)); // 0110 -> 2 ones (even)
6
    assertFalse(BitHacks.getParity(0)); // 0 ones (even)
7
    assertFalse(BitHacks.getParity(-1)); // 32 ones (even)
8
    assertTrue(BitHacks.getParity(Integer.MAX_VALUE)); // 31 ones (odd)
9
}

(Integer.bitCount(v) % 2) != 0;

1
/**
2
 * ### 25. 通过异或(XOR)交换两个整数的值 ###
3
 * 注意：a和b不能是同一个内存地址的引用。
4
 * @param a 第一个整数的单元素数组。
5
 * @param b 第二个整数的单元素数组。
6
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesXOR">Original C version</a>
7
 */
8
public static void swapWithXOR(int[] a, int[] b) {
9
    if (a == b) return;
10
    a[0] ^= b[0];
11
    b[0] ^= a[0];
12
    a[0] ^= b[0];
13
}

1
@Test
2
@DisplayName("25. 通过异或(XOR)交换两个整数的值")
3
void testSwapWithXOR() {
4
    int[] a = {10};
5
    int[] b = {20};
6
    BitHacks.swapWithXOR(a, b);
7
    assertEquals(20, a[0]);
8
    assertEquals(10, b[0]);
9
}

1
/**
2
 * ### 26. 通过异或(XOR)交换一个整数内部的两个位序列 ###
3
 * @param b 原始整数。
4
 * @param i 第一个位序列的起始位置。
5
 * @param j 第二个位序列的起始位置。
6
 * @param n 位序列的长度。
7
 * @return 交换后的整数。
8
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#SwappingBitsXOR">Original C version</a>
9
 */
10
public static int swapBitSequences(int b, int i, int j, int n) {
11
    int x = ((b >>> i) ^ (b >>> j)) & ((1 << n) - 1);
12
    return b ^ ((x << i) | (x << j));
13
}

1
@Test
2
@DisplayName("26. 通过异或(XOR)交换一个整数内部的两个位序列")
3
void testSwapBitSequences() {
4
    // b = 00101111, i=1, j=5, n=3 -> swap 001 with 111
5
    // expected: 11100011
6
    int b = 0b00101111;
7
    int expected = 0b11100011;
8
    assertEquals(expected, BitHacks.swapBitSequences(b, 1, 5, 3));
9
}

1
/**
2
 * ### 32. 并行反转一个32位整数的所有位 ###
3
 * @param v 待反转的32位整数。
4
 * @return 反转后的整数。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel">Original C version</a>
6
 */
7
public static int reverseBits(int v) {
8
    v = ((v >>> 1) & 0x55555555) | ((v & 0x55555555) << 1);
9
    v = ((v >>> 2) & 0x33333333) | ((v & 0x33333333) << 2);
10
    v = ((v >>> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
11
    v = ((v >>> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
12
    v = (v >>> 16) | (v << 16);
13
    return v;
14
}

1
@Test
2
@DisplayName("32. 并行反转一个32位整数的所有位")
3
void testReverseBits() {
4
    assertEquals(0, BitHacks.reverseBits(0));
5
    assertEquals(0x80000000, BitHacks.reverseBits(1));
6
    assertEquals(0x40000000, BitHacks.reverseBits(2));
7
    assertEquals(-1, BitHacks.reverseBits(-1));
8
    assertEquals(0x55555555, BitHacks.reverseBits(0xAAAAAAAA));
9
}

Integer.reverse(v)

1
/**
2
 * ### 34. 计算 n % d, 其中 d = 2^s - 1 ###
3
 * @param n 分子。
4
 * @param s d = (1 << s) - 1。
5
 * @return n % d。
6
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#ModulusDivision">Original C version</a>
7
 */
8
public static int modulusByPowerOf2Minus1(int n, int s) {
9
    if (s <= 0 || s >= 32) throw new IllegalArgumentException("s must be between 1 and 31");
10
    int d = (1 << s) - 1;
11
    if (d == 0) return 0;
12
    int m = n;
13
    while (n > d) {
14
        m = 0;
15
        int tempN = n;
16
        while (tempN > 0) {
17
            m += tempN & d;
18
            tempN >>>= s;
19
        }
20
        n = m;
21
    }
22
    return m == d ? 0 : m;
23
}

1
@Test
2
@DisplayName("34. 计算 n % d, 其中 d = 2^s - 1")
3
void testModulusByPowerOf2Minus1() {
4
    assertEquals(100 % 7, BitHacks.modulusByPowerOf2Minus1(100, 3)); // s=3, d=7
5
    assertEquals(12345 % 31, BitHacks.modulusByPowerOf2Minus1(12345, 5)); // s=5, d=31
6
    assertEquals(99 % 1, BitHacks.modulusByPowerOf2Minus1(99, 1)); // s=1, d=1
7
}

1
/**
2
 * ### 40. 使用 De Bruijn 序列和乘法查找计算整数的log₂ ###
3
 * @param v 待计算的32位正整数。
4
 * @return log₂(v)。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn">Original C version</a>
6
 */
7
public static int log2WithDeBruijn(int v) {
8
    final int[] DE_BRUIJN_TABLE = {
9
        0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
10
        8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
11
    };
12
    v |= v >>> 1;
13
    v |= v >>> 2;
14
    v |= v >>> 4;
15
    v |= v >>> 8;
16
    v |= v >>> 16;
17
    return DE_BRUIJN_TABLE[(v * 0x07C4ACDD) >>> 27];
18
}

1
@Test
2
@DisplayName("40. 使用 De Bruijn 序列计算log₂")
3
void testLog2WithDeBruijn() {
4
    assertEquals(0, BitHacks.log2WithDeBruijn(1));
5
    assertEquals(1, BitHacks.log2WithDeBruijn(2));
6
    assertEquals(4, BitHacks.log2WithDeBruijn(16));
7
    assertEquals(4, BitHacks.log2WithDeBruijn(20)); // floor(log2(20)) = 4
8
    assertEquals(30, BitHacks.log2WithDeBruijn(Integer.MAX_VALUE));
9
}

1
31 - Integer.numberOfLeadingZeros(v);

1
/**
2
 * ### 41. 计算整数的log₁₀ ###
3
 * @param v 待计算的32位正整数。
4
 * @return log₁₀(v)。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10">Original C version</a>
6
 */
7
public static int log10(int v) {
8
    if (v <= 0) throw new IllegalArgumentException("v must be positive");
9
    final int[] POWERS_OF_10 = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
10
    int log2 = 31 - Integer.numberOfLeadingZeros(v);
11
    int t = (log2 + 1) * 1233 >>> 12;
12
    return t - (v < POWERS_OF_10[t] ? 1 : 0);
13
}

1
@Test
2
@DisplayName("41. 计算整数的log₁₀")
3
void testLog10() {
4
    assertEquals(0, BitHacks.log10(9));
5
    assertEquals(1, BitHacks.log10(10));
6
    assertEquals(2, BitHacks.log10(100));
7
    assertEquals(2, BitHacks.log10(999));
8
    assertEquals(3, BitHacks.log10(1000));
9
    assertEquals(9, BitHacks.log10(Integer.MAX_VALUE));
10
}

1
Math.log10(v)

1
/**
2
 * ### 50. 使用 De Bruijn 序列和乘法查找计算末尾连续0的数量 ###
3
 * @param v 待计算的32位整数。
4
 * @return 末尾连续0的数量。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup">Original C version</a>
6
 */
7
public static int countTrailingZeros(int v) {
8
    final int[] DE_BRUIJN_TABLE = {
9
         0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
10
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
11
    };
12
    if (v == 0) return 32;
13
    return DE_BRUIJN_TABLE[(((v & -v) * 0x077CB531)) >>> 27];
14
}

1
@Test
2
@DisplayName("50. 计算末尾连续0的数量")
3
void testCountTrailingZeros() {
4
    assertEquals(32, BitHacks.countTrailingZeros(0));
5
    assertEquals(0, BitHacks.countTrailingZeros(1));
6
    assertEquals(1, BitHacks.countTrailingZeros(2));
7
    assertEquals(3, BitHacks.countTrailingZeros(8));
8
    assertEquals(0, BitHacks.countTrailingZeros(-1));
9
    assertEquals(31, BitHacks.countTrailingZeros(Integer.MIN_VALUE));
10
}

1
// Integer.numberOfTrailingZeros(v)
2
@HotSpotIntrinsicCandidate
3
public static int numberOfTrailingZeros(int i) {
4
    // HD, Figure 5-14
5
    int y;
6
    if (i == 0) return 32;
7
    int n = 31;
8
    y = i <<16; if (y != 0) { n = n -16; i = y; }
9
    y = i << 8; if (y != 0) { n = n - 8; i = y; }
10
    y = i << 4; if (y != 0) { n = n - 4; i = y; }
11
    y = i << 2; if (y != 0) { n = n - 2; i = y; }
12
    return n - ((i << 1) >>> 31);
13
}

1
/**
2
 * ### 52. 向上取整到下一个2的幂 ###
3
 * @param v 待计算的32位整数。
4
 * @return 大于或等于v的最小的2的幂。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2">Original C version</a>
6
 */
7
public static int roundUpToPowerOfTwo(int v) {
8
    if (v == 0) return 1;
9
    v--;
10
    v |= v >>> 1;
11
    v |= v >>> 2;
12
    v |= v >>> 4;
13
    v |= v >>> 8;
14
    v |= v >>> 16;
15
    v++;
16
    return v;
17
}

1
@Test
2
@DisplayName("52. 向上取整到下一个2的幂")
3
void testRoundUpToPowerOfTwo() {
4
    assertEquals(1, BitHacks.roundUpToPowerOfTwo(0));
5
    assertEquals(1, BitHacks.roundUpToPowerOfTwo(1));
6
    assertEquals(2, BitHacks.roundUpToPowerOfTwo(2));
7
    assertEquals(4, BitHacks.roundUpToPowerOfTwo(3));
8
    assertEquals(8, BitHacks.roundUpToPowerOfTwo(7));
9
    assertEquals(8, BitHacks.roundUpToPowerOfTwo(8));
10
    assertEquals(1024, BitHacks.roundUpToPowerOfTwo(1000));
11
    assertEquals(1 << 30, BitHacks.roundUpToPowerOfTwo((1 << 30) - 1));
12
}

1
v > 0 ? Integer.highestOneBit(v - 1) << 1 : 1;

1
/**
2
 * ### 56. 使用二进制魔数交错两个16位整数的位，生成32位莫顿码 ###
3
 * @param x 第一个16位整数 (放入偶数位)。
4
 * @param y 第二个16位整数 (放入奇数位)。
5
 * @return 32位莫顿码。
6
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN">Original C version</a>
7
 */
8
public static int interleaveBits(int x, int y) {
9
    //x and y must be < 65536
10
    x = (x | (x << 8)) & 0x00FF00FF;
11
    x = (x | (x << 4)) & 0x0F0F0F0F;
12
    x = (x | (x << 2)) & 0x33333333;
13
    x = (x | (x << 1)) & 0x55555555;
14

15
    y = (y | (y << 8)) & 0x00FF00FF;
16
    y = (y | (y << 4)) & 0x0F0F0F0F;
17
    y = (y | (y << 2)) & 0x33333333;
18
    y = (y | (y << 1)) & 0x55555555;
19

20
    return x | (y << 1);
21
}

1
@Test
2
@DisplayName("56. 交错位 (莫顿码)")
3
void testInterleaveBits() {
4
    // x=1 (0001), y=2 (0010) -> z = ...010010 -> 18
5
    assertEquals(18, BitHacks.interleaveBits(1, 2));
6
    // x=2 (0010), y=3 (0011) -> z = ...011010 -> 26
7
    assertEquals(26, BitHacks.interleaveBits(2, 3));
8
}

1
/**
2
 * ### 57. 判断一个字中是否含有0字节 ###
3
 * @param v 待检查的整数。
4
 * @return 如果含有0字节则返回true。
5
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord">Original C version</a>
6
 */
7
public static boolean hasZeroByte(int v) {
8
    return ((v - 0x01010101) & ~v & 0x80808080) != 0;
9
}

1
@Test
2
@DisplayName("57. 判断一个字中是否含有0字节")
3
void testHasZeroByte() {
4
    assertTrue(BitHacks.hasZeroByte(0x12345600));
5
    assertTrue(BitHacks.hasZeroByte(0x00345678));
6
    assertTrue(BitHacks.hasZeroByte(0x12005678));
7
    assertFalse(BitHacks.hasZeroByte(0x12345678));
8
    assertFalse(BitHacks.hasZeroByte(-1));
9
}

1
/**
2
 * ### 58. 判断一个整数中是否有等于n的字节 ###
3
 * @param x 待检查的整数。
4
 * @param n 目标字节值 (0-255)。
5
 * @return 如果含有等于n的字节则返回true。
6
 * @see <a href="https://graphics.stanford.edu/~seander/bithacks.html#ValueInWord">Original C version</a>
7
 */
8
public static boolean hasValueByte(int x, int n) {
9
    int mask = 0x01010101 * (n & 0xFF);
10
    // 参考 22. 判断一个字中是否含有0字节
11
    return hasZeroByte(x ^ mask);
12
}

1
@Test
2
@DisplayName("58. 判断一个字中是否有等于n的字节")
3
void testHasValueByte() {
4
    assertTrue(BitHacks.hasValueByte(0x12345678, 0x12));
5
    assertTrue(BitHacks.hasValueByte(0x12345678, 0x34));
6
    assertTrue(BitHacks.hasValueByte(0x12345678, 0x56));
7
    assertTrue(BitHacks.hasValueByte(0x12345678, 0x78));
8
    assertFalse(BitHacks.hasValueByte(0x12345678, 0x99));
9
}