Count the one bits in an integer

Go down

Count the one bits in an integer

Post  viterbi on Tue Sep 13, 2011 10:03 am

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

View user profile

Back to top Go down

Re: Count the one bits in an integer

Post  viterbi on Tue Sep 13, 2011 10:04 am

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___}

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Count the one bits in an integer

Post  Admin on Tue Sep 13, 2011 2:04 pm

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____}

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Re: Count the one bits in an integer

Post  viterbi on Thu Sep 15, 2011 11:28 pm

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

View user profile

Back to top Go down

Re: Count the one bits in an integer

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum