Redis 源码学习 -- rev 二进制翻转函数

发表于 更新于 阅读次数：

redis学习笔记

基于 Redis 6.0.4

1
redis / src / dict.c

源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* Function to reverse bits. Algorithm from:
 * http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
static unsigned long rev(unsigned long v) {
    // CHAR_BIT = __CHAR_BIT__ = 8
    // 在 32 位下 s = 32，在 64 位下s = 64
    unsigned long s = CHAR_BIT * sizeof(v); // bit size; must be power of 2
    // 32 位或者 64 位全 1
    unsigned long mask = ~0UL;
    while ((s >>= 1) > 0) { // 除 2
        mask ^= (mask << s); // 掩码取半
        // 对入参的高位部分和低位部分分别进行计算后完成对换
        v = ((v >> s) & mask) | ((v << s) & ~mask);
    }
    return v;
}

rev() 位于 Redis 底层数据结构 dict 的实现中作为辅助函数出现，作用是翻转二进制。

总体思路是: 用迭代的思想将 64 位的二进制数先将高 32 位和低 32 位对换，然后将高 32 位二进制数的高 16 位和低 16 位对换，低 32 位类似，再讲高 16 位的二进制数的高 8 位和低 8 位对换，以此类推完成翻转。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>                                                                             
 
// 打印二进制
void printBits(const unsigned long v) {
    unsigned long mask = 1UL << (sizeof(v) * 8 - 1);
    while ((mask) > 0) {
        int bit = (v & mask) ? 1 : 0;
        printf("%d", bit);
        mask >>= 1;
    }
    printf("\n");
}                                                                        
 
static unsigned long rev(unsigned long v) {
    unsigned long s = 8 * sizeof(v); // bit size; must be power of 2
    unsigned long mask = ~0UL;
    printf("orig v                       = ");
    printBits(v);
    printf("orig s                       = ");
    printBits(s);
    printf("orig mask                    = ");
    printBits(mask);
 
    while ((s >>= 1) > 0) {
        printf("\n");
 
        printf("mask << s                    = ");
        printBits(mask << s);
 
        mask ^= (mask << s);
 
        printf("mask ^ (mask << s)           = ");
        printBits(mask);
 
        printf("(v >> s)                     = ");
        printBits(v >> s);
        printf("(v >> s) & mask              = ");
        printBits((v >> s) & mask);
 
        printf("(v << s)                     = ");
        printBits(v << s);
        printf("(v << s) & ~mask             = ");
        printBits((v << s) & ~mask);
 
        v = ((v >> s) & mask) | ((v << s) & ~mask);
 
        printf("((v>>s)&mask)|((v<<s)&~mask) = ");
        printBits(v);
 
        printf("\n");
        printf("v                            = ");
        printBits(v);
        printf("s                            = ");
        printBits(s);
        printf("mask                         = ");
        printBits(mask);
    }
 
    return v;
}

int main() {
    unsigned long i = 0x9988776655443322;
    i = rev(i);
 
    return 0;
}

以下是 output:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
➜  test ./a.out 
orig v                       = 1001100110001000011101110110011001010101010001000011001100100010
orig s                       = 0000000000000000000000000000000000000000000000000000000001000000
orig mask                    = 1111111111111111111111111111111111111111111111111111111111111111

mask << s                    = 1111111111111111111111111111111100000000000000000000000000000000
mask ^ (mask << s)           = 0000000000000000000000000000000011111111111111111111111111111111
(v >> s)                     = 0000000000000000000000000000000010011001100010000111011101100110
(v >> s) & mask              = 0000000000000000000000000000000010011001100010000111011101100110
(v << s)                     = 0101010101000100001100110010001000000000000000000000000000000000
(v << s) & ~mask             = 0101010101000100001100110010001000000000000000000000000000000000
((v>>s)&mask)|((v<<s)&~mask) = 0101010101000100001100110010001010011001100010000111011101100110

v                            = 0101010101000100001100110010001010011001100010000111011101100110
s                            = 0000000000000000000000000000000000000000000000000000000000100000
mask                         = 0000000000000000000000000000000011111111111111111111111111111111

mask << s                    = 0000000000000000111111111111111111111111111111110000000000000000
mask ^ (mask << s)           = 0000000000000000111111111111111100000000000000001111111111111111
(v >> s)                     = 0000000000000000010101010100010000110011001000101001100110001000
(v >> s) & mask              = 0000000000000000010101010100010000000000000000001001100110001000
(v << s)                     = 0011001100100010100110011000100001110111011001100000000000000000
(v << s) & ~mask             = 0011001100100010000000000000000001110111011001100000000000000000
((v>>s)&mask)|((v<<s)&~mask) = 0011001100100010010101010100010001110111011001101001100110001000

v                            = 0011001100100010010101010100010001110111011001101001100110001000
s                            = 0000000000000000000000000000000000000000000000000000000000010000
mask                         = 0000000000000000111111111111111100000000000000001111111111111111

mask << s                    = 0000000011111111111111110000000000000000111111111111111100000000
mask ^ (mask << s)           = 0000000011111111000000001111111100000000111111110000000011111111
(v >> s)                     = 0000000000110011001000100101010101000100011101110110011010011001
(v >> s) & mask              = 0000000000110011000000000101010100000000011101110000000010011001
(v << s)                     = 0010001001010101010001000111011101100110100110011000100000000000
(v << s) & ~mask             = 0010001000000000010001000000000001100110000000001000100000000000
((v>>s)&mask)|((v<<s)&~mask) = 0010001000110011010001000101010101100110011101111000100010011001

v                            = 0010001000110011010001000101010101100110011101111000100010011001
s                            = 0000000000000000000000000000000000000000000000000000000000001000
mask                         = 0000000011111111000000001111111100000000111111110000000011111111

mask << s                    = 0000111111110000000011111111000000001111111100000000111111110000
mask ^ (mask << s)           = 0000111100001111000011110000111100001111000011110000111100001111
(v >> s)                     = 0000001000100011001101000100010101010110011001110111100010001001
(v >> s) & mask              = 0000001000000011000001000000010100000110000001110000100000001001
(v << s)                     = 0010001100110100010001010101011001100111011110001000100110010000
(v << s) & ~mask             = 0010000000110000010000000101000001100000011100001000000010010000
((v>>s)&mask)|((v<<s)&~mask) = 0010001000110011010001000101010101100110011101111000100010011001

v                            = 0010001000110011010001000101010101100110011101111000100010011001
s                            = 0000000000000000000000000000000000000000000000000000000000000100
mask                         = 0000111100001111000011110000111100001111000011110000111100001111

mask << s                    = 0011110000111100001111000011110000111100001111000011110000111100
mask ^ (mask << s)           = 0011001100110011001100110011001100110011001100110011001100110011
(v >> s)                     = 0000100010001100110100010001010101011001100111011110001000100110
(v >> s) & mask              = 0000000000000000000100010001000100010001000100010010001000100010
(v << s)                     = 1000100011001101000100010101010110011001110111100010001001100100
(v << s) & ~mask             = 1000100011001100000000000100010010001000110011000000000001000100
((v>>s)&mask)|((v<<s)&~mask) = 1000100011001100000100010101010110011001110111010010001001100110

v                            = 1000100011001100000100010101010110011001110111010010001001100110
s                            = 0000000000000000000000000000000000000000000000000000000000000010
mask                         = 0011001100110011001100110011001100110011001100110011001100110011

mask << s                    = 0110011001100110011001100110011001100110011001100110011001100110
mask ^ (mask << s)           = 0101010101010101010101010101010101010101010101010101010101010101
(v >> s)                     = 0100010001100110000010001010101011001100111011101001000100110011
(v >> s) & mask              = 0100010001000100000000000000000001000100010001000001000100010001
(v << s)                     = 0001000110011000001000101010101100110011101110100100010011001100
(v << s) & ~mask             = 0000000010001000001000101010101000100010101010100000000010001000
((v>>s)&mask)|((v<<s)&~mask) = 0100010011001100001000101010101001100110111011100001000110011001

v                            = 0100010011001100001000101010101001100110111011100001000110011001
s                            = 0000000000000000000000000000000000000000000000000000000000000001
mask                         = 0101010101010101010101010101010101010101010101010101010101010101