int sum_of_1(int x) {
int res = 0;
while (x != 0) res++, x -= lowbit(x);
return res;
}
I come up with two methods.
A method is using a varible to count the sum, whenever you push, you maintain the varible, the change of the varible depends on what you push and what will pop.
Another method is an algorithm called "lowbit"
int lowbit(int x) {
return x & -x;
}
it will return the last 1 int the binary representation of the x.
So this can get the number of '1' in the binary representation of x.
for example, code like this.
int sum_of_1(int x) {
int res = 0;
while (x != 0) res++, x -= lowbit(x);
return res;
}
// count the number of bits set in v
unsigned char sum( unsigned char v )
{
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}
return c; // c has the count, v is zero
}
unsigned char push( unsigned char v, bool in )
{
v << 1;
if( in )
{
v |= 1;
}
return v;
}
Counting bits set, Brian Kernighan's way
// count the number of bits set in v
unsigned char sum( unsigned char v )
{
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}
return c; // c has the count, v is zero
}
unsigned char push( unsigned char v, bool in )
{
v << 1;
if( in )
{
v |= 1;
}
return v;
}
发布评论
评论（2）
我想出了两种方法。
一种方法是使用一个变量来计算总和，每当您压入时，您都会维护该变量，变量的变化取决于您压入的内容和弹出的内容。
另一种方法是一种称为“lowbit”的算法，
它将返回 x 的二进制表示形式的最后 1 个 int。
这样就可以得到x的二进制表示中'1'的个数。
例如，这样的代码。
I come up with two methods.
A method is using a varible to count the sum, whenever you push, you maintain the varible, the change of the varible depends on what you push and what will pop.
Another method is an algorithm called "lowbit"
it will return the last 1 int the binary representation of the x.
So this can get the number of '1' in the binary representation of x.
for example, code like this.
计算位设置，Brian Kernighan 的方式
Counting bits set, Brian Kernighan's way