leetcode/src/191.c at master · lennylxx/leetcode · GitHub

Name: leetcode/src/191.c at master · lennylxx/leetcode · GitHub
Rating: 4.4 (2898 reviews)
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
#include<stdio.h>
#include<stdint.h>

/*
 1. https://graphics.stanford.edu/~seander/bithacks.html
 2. Hacker's Delight 2nd Edition, Chapter 5. Counting Bits
*/

voidprint_bits(uint32_tn) {
inti=32;
while(i--){
if ((n >> i) &1)
printf("1");
else
printf("0");
 }
printf("\n");
}

/* O(logn) */
inthammingWeight_1(uint32_tn) {
intret=0;
while (n) {
ret+=n&0x01;
n >>= 1;
 }
returnret;
}

/* O(m) */
inthammingWeight_2(uint32_tn) {
intret=0;
while (n) {
n=n& (n-1);
ret++;
 }
returnret;
}

/*****************************
 Code to count 0 bits

 while (n != 0xFFFFFFFF) {
 n = n | (n + 1);
 ret++;
 }

Or,

 n = ~n;
 count1Bits(n);

******************************/

/* 5 steps */
inthammingWeight_3(uint32_tn) {
uint32_tt=n;
/* add up odd and even bits 1 bit */
t= ((t&0xAAAAAAAA) >> 1) + (t&0x55555555);
/* 2 bits */
t= ((t&0xCCCCCCCC) >> 2) + (t&0x33333333);
/* 4 bits */
t= ((t&0xF0F0F0F0) >> 4) + (t&0x0F0F0F0F);
/* 8 bits */
t= ((t&0xFF00FF00) >> 8) + (t&0x00FF00FF);
/* 16 bits */
t= ((t&0xFFFF0000) >> 16) + (t&0x0000FFFF);

returnt;
}

/* simplification of hammingWeight_3 */
inthammingWeight_4(uint32_tn) {
n=n- ((n >> 1) &0x55555555);
n= (n&0x33333333) + ((n >> 2) &0x33333333);
n= (n+ (n >> 4)) &0x0F0F0F0F;
n=n+ (n >> 8);
n=n+ (n >> 16);
returnn&0x0000003F;
}

/* HAKMEM */
inthammingWeight_5(uint32_tn) {
uint32_tt;
t= (n >> 1) &033333333333; // Count bits in
n=n-t; // each 3-bit
t= (t >> 1) &033333333333; // field.
n=n-t;
n= (n+ (n >> 3)) &030707070707;
returnn % 63; // Add 6-bit sums.
//((n * 0404040404) >> 26) + (n >> 30)
}

/* variation of HAKMEM */
inthammingWeight(uint32_tn) {
uint32_tt;
t= (n >> 1) &0x77777777; // Count bits in
n=n-t; // each 4-bit
t= (t >> 1) &0x77777777; // field.
n=n-t;
t= (t >> 1) &0x77777777;
n=n-t;
n= (n+ (n >> 4)) &0x0F0F0F0F; // Get byte sums.
n=n*0x01010101; // Add the bytes.
returnn >> 24;
}

intmain() {
uint32_tn=11;
printf("%d\n", hammingWeight(n));
return0;
}