1 /* ===-- popcountdi2.c - Implement __popcountdi2 ----------------------------===
3 * The LLVM Compiler Infrastructure
5 * This file is dual licensed under the MIT and the University of Illinois Open
6 * Source Licenses. See LICENSE.TXT for details.
8 * ===----------------------------------------------------------------------===
10 * This file implements __popcountdi2 for the compiler_rt library.
12 * ===----------------------------------------------------------------------===
17 /* Returns: count of 1 bits */
19 COMPILER_RT_ABI si_int
20 __popcountdi2(di_int a
)
22 du_int x2
= (du_int
)a
;
23 x2
= x2
- ((x2
>> 1) & 0x5555555555555555uLL
);
24 /* Every 2 bits holds the sum of every pair of bits (32) */
25 x2
= ((x2
>> 2) & 0x3333333333333333uLL
) + (x2
& 0x3333333333333333uLL
);
26 /* Every 4 bits holds the sum of every 4-set of bits (3 significant bits) (16) */
27 x2
= (x2
+ (x2
>> 4)) & 0x0F0F0F0F0F0F0F0FuLL
;
28 /* Every 8 bits holds the sum of every 8-set of bits (4 significant bits) (8) */
29 su_int x
= (su_int
)(x2
+ (x2
>> 32));
30 /* The lower 32 bits hold four 16 bit sums (5 significant bits). */
31 /* Upper 32 bits are garbage */
33 /* The lower 16 bits hold two 32 bit sums (6 significant bits). */
34 /* Upper 16 bits are garbage */
35 return (x
+ (x
>> 8)) & 0x0000007F; /* (7 significant bits) */