部分 Java 位运算函数的 C++ 实现

Java 语言中有许多位运算函数,比如 highestOneBit 就是 Fenwick 树中的 lowbit 的反面形式,即 highbit。我从 Matrix67 的博客中抽出了下面这三个函数,当我将 Java 代码转换成 C++ 时,或许会用到它们。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int bitCount(int x)
{
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
    x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
    return x;
}
int numberOfLeadingZeros(unsigned x)
{
    if (x == 0) return 32;
    int n = 1;
    if ((x >> 16) == 0) {n += 16; x <<= 16;}
    if ((x >> 24) == 0) {n += 8; x <<= 8;}
    if ((x >> 28) == 0) {n += 4; x <<= 4;}
    if ((x >> 30) == 0) {n += 2; x <<= 2;}
    n -= (x >> 31);
    return n;
}
int reverse(int x)
{
    x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1;
    x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2;
    x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4;
    x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8;
    x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;
    return x;
}

  

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。