GCC内建函数C语言实现__builtin_popcountll，__builtin_ctzll，__buitlin_clzll

C语言编程有时需要用到__builtin_popcountll，__builtin_ctzll，__buitlin_clzll等GCC内建函数，这里给出了简单的实现代码，算法实现不一定是最优的但可以使用，大端模式CPU没有验证！！

/**
哈希表
记录0~255每个数的二进制表示1的个数
如：1,0b0001  有1个1
    2,0b0010  有1个1
    3,0b0011  有2个1
*/
int poptable[256] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

// big - endian和little - endian
enum {
    E_CPU_BIG_ENDIAN = 0, // 大端模式
    E_CPU_LITTLE_ENDIAN = 1   // 小端模式
};

/*
判断CPU大小端模式
小端模式中：低位字节放在低地址，高位字节放在高地址；little-endian
大端模式中，低位字节放在高地址，高位字节放在低地址；big-endian
*/
char cpu_endian(void)
{
    union {
        int a;
        char b;
    }c;

    c.a = 1;
    if (c.b == 1) {
        /* CPU 是 小端模式 */
        return E_CPU_LITTLE_ENDIAN;
    }
    else {

        /* CPU 是 大端模式 */
        return E_CPU_BIG_ENDIAN;
    }

    return 0;
}

/* 
计算x以二进制表示法包含1的个数
*/
int __builtin_popcountll(unsigned long long x) 
{
    int count = 0;
    int i = 0;
    for (i = 0; i < 8; i++) {
        count += poptable[(x >> (8 * i)) & 0xff];
    }
    return count;
}

/**
计算 x 二进制表示形式中末尾0的个数。
*/
int __builtin_ctzll(unsigned long long x)
{
    
    // 0x1122334455667788
    // 2,6,10,14  后面有1个零
    // 4,12 后面有2个零
    // 8 后面有3个零
    /*
        0000    0       0
        0001    1       1
        0010    2       2
        0011    3       3
        0100    4       4
        0101    5       5
        0110    6       6
        0111    7       7
        1000    8       8
        1001    9       9
        1010    10      A
        1011    11      B
        1100    12      C
        1101    13      D
        1110    14      E
        1111    15      F
    */

    int count = 0;
    if (cpu_endian() == E_CPU_BIG_ENDIAN)
    {
        // 大端模式  数据转成小端模式，即数据高低字节对调
        // 0x1122334455667788
        // 0x8877665544332211
        x = (((x >> 56) & 0xFF) | (((x >> 48) & 0xFF) << 8) | (((x >> 40) & 0xFF) << 16) | (((x >> 32) & 0xFF) << 24) | (((x >> 24) & 0xFF) << 32) | (((x >> 16) & 0xFF) << 40) | (((x >> 8) & 0xFF) << 48) | ((x & 0xFF) << 56));    
    }
    else 
    {
        // 小端模式
    }
    int i = 0;
    for (i = 0; i < 8; i++) {
        unsigned char j = (x>>(i*8) & 0xFF);
        if (0 == j) {
            count += 8;
        }
        else 
        {
            unsigned char n=0;
            unsigned char L = (j & 0x0F);
            unsigned char H = ((j>>4) & 0x0F);
            n = L;
            if (0 == L) {
                count += 4;
                n = H;
            }
            // 2,6,10,14  后面有1个零
            if ((2 == n) || (6 == n) || (10 == n) || (14 == n)) {
                count += 1;
            }
            // 4,12 后面有2个零
            else if ((4==n)||(12==n)) 
            {
                count += 2;
            }
            // 8 后面有3个零
            else if (8==n) 
            {
                count += 3;
            }
            break;
        }       
    }
    return count;
}

/* 返回括号内数的二进制表示形式中前导0的个数。 */
int __buitlin_clzll(unsigned long long x)
{
    // 0x1122334455667788
    // 4,5,6,7  前面有1个零
    // 2,3      前面有2个零
    // 1        前面有3个零
   
    /*
        0000    0       0
        0001    1       1
        0010    2       2
        0011    3       3
        0100    4       4
        0101    5       5
        0110    6       6
        0111    7       7
        1000    8       8
        1001    9       9
        1010    10      A
        1011    11      B
        1100    12      C
        1101    13      D
        1110    14      E
        1111    15      F
    */
    // 0x000000000120
    int count = 0;
    if (cpu_endian() == E_CPU_BIG_ENDIAN)
    {
        // 大端模式  数据转成小端模式，即数据高低字节对调
        // 0x1122334455667788
        // 0x8877665544332211
        x = (((x >> 56) & 0xFF) | (((x >> 48) & 0xFF) << 8) | (((x >> 40) & 0xFF) << 16) | (((x >> 32) & 0xFF) << 24) | (((x >> 24) & 0xFF) << 32) | (((x >> 16) & 0xFF) << 40) | (((x >> 8) & 0xFF) << 48) | ((x & 0xFF) << 56));
    }
    else
    {
        // 小端模式
    }
    
    int i = 0;
    for (i = 7; i >= 0; i--) {
        unsigned char j = ((x >> (i * 8)) & 0xFF);
        if (0 == j) {
            count += 8;
        }
        else 
        {
            unsigned char n = 0;
            unsigned char L = (j & 0xF);
            unsigned char H = (j >> 4) & 0xF;
            
            if (0 == H) {
                count += 4;
                n = L;
            }
            // 4,5,6,7  前面有1个零
            // 2,3      前面有2个零
            // 1        前面有3个零
            if (1 == n) {
                count += 3;
            }
            else if ((2 == n) || (3 == n)) {
                count += 2;
            }
            else if ((4 == n) || (5 == n) || (6 == n) || (7 == n)) {
                count += 1;
            }
            break;
        }
    }
    return count;
}

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222