Count the one bits in an integer
2 posters
Page 1 of 1
Count the one bits in an integer
Regular way:
1____int ones(int x) {
2__________unsigned int y = x;
3__________int count = 0;
4__________while (y != 0) {
5________________if (y&1 == 1) { count++; }
6________________y >>= 1;
7__________}
8__________return count;
9____}
1____int ones(int x) {
2__________unsigned int y = x;
3__________int count = 0;
4__________while (y != 0) {
5________________if (y&1 == 1) { count++; }
6________________y >>= 1;
7__________}
8__________return count;
9____}
viterbi- Posts : 32
Join date : 2011-09-03
Re: Count the one bits in an integer
Faster way:
1____const int p[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
2____
3____int ones3(int x) {
4__________int mask = 0x0000000f;
5__________int count = p[x&mask];
6__________x >>= 4;
7__________count += p[x&mask];
8__________x >>= 4;
9__________count += p[x&mask];
10_________x >>= 4;
11_________count += p[x&mask];
12_________x >>= 4;
13_________count += p[x&mask];
14_________x >>= 4;
15_________count += p[x&mask];
16_________x >>= 4;
17_________count += p[x&mask];
18_________x >>= 4;
19_________count += p[x&mask];
20_________return count;
21___}
1____const int p[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
2____
3____int ones3(int x) {
4__________int mask = 0x0000000f;
5__________int count = p[x&mask];
6__________x >>= 4;
7__________count += p[x&mask];
8__________x >>= 4;
9__________count += p[x&mask];
10_________x >>= 4;
11_________count += p[x&mask];
12_________x >>= 4;
13_________count += p[x&mask];
14_________x >>= 4;
15_________count += p[x&mask];
16_________x >>= 4;
17_________count += p[x&mask];
18_________x >>= 4;
19_________count += p[x&mask];
20_________return count;
21___}
viterbi- Posts : 32
Join date : 2011-09-03
Re: Count the one bits in an integer
Here when unsigned int y is the reference of int x,
if x is negative, the leftest digit should be 1, but for unsigned int the leftest digit should be 0.
So in this step, will the leftest digit changes from 1 to 0?
if x is negative, the leftest digit should be 1, but for unsigned int the leftest digit should be 0.
So in this step, will the leftest digit changes from 1 to 0?
viterbi wrote:Regular way:
1____int ones(int x) {
2__________unsigned int y = x;
3__________int count = 0;
4__________while (y != 0) {
5________________if (y&1 == 1) { count++; }
6________________y >>= 1;
7__________}
8__________return count;
9____}
Re: Count the one bits in an integer
For unsigned int, the leftest digit could be 1. Since it don't have sign bit, it has one more bit for value. The range of int is -2^31~2^31-1. The range of unsigned int is 0 ~ 2^32-1.
Admin wrote:Here when unsigned int y is the reference of int x,
if x is negative, the leftest digit should be 1, but for unsigned int the leftest digit should be 0.
So in this step, will the leftest digit changes from 1 to 0?viterbi wrote:Regular way:
1____int ones(int x) {
2__________unsigned int y = x;
3__________int count = 0;
4__________while (y != 0) {
5________________if (y&1 == 1) { count++; }
6________________y >>= 1;
7__________}
8__________return count;
9____}
viterbi- Posts : 32
Join date : 2011-09-03
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|