用于计算设定位数的功能 [英] function to count number of set bits
问题描述
我想知道是否有人知道以下功能是否可以作为非2s补充机器上的固定位计数器正常运行
（作为K& ; R2暗示）。
| int bitcount（unsigned x）
| {
| int count;
|
| for（count = 0; x！= 0; count ++，x& =（x-1））
| ;
|
|返回计数;
| }
我无法想象为什么这会在1s补充或
sign-mag机器上失败的原因（并且找不到）一个非2s赞美机器试试它/ b
）。就C来说它是否可移植？
而且，如果我在主程序中声明一个signed int并且想要将msb设置为
1，我可以这样做（32位整数）吗？：
int b = 0x8000000;
/ *是0x80000000作为无符号长整数或者a签了
int？ * /
int count = bitcount（b）;
/ *这是未定义的 - 试图将负数int发送给bitcount
功能？ * /
Hi, I''m wondering if anyone knows if the following function will
function properly as a set-bit counter on non 2s complement machines
(as K&R2 implies).
| int bitcount(unsigned x)
| {
| int count;
|
| for(count = 0; x != 0; count++, x &= (x-1))
| ;
|
| return count;
| }
I can''t think of a reason why this would fail on a 1s complement or
sign-mag machine (and can''t find a non 2s compliment machine to try it
on). Is it portable as far as C is concerned?
And also, if I declare a signed int in the main program and want to set
the msb to 1, can I do this (32bit ints)?:
int b = 0x8000000;
/* is the 0x80000000 taken as an unsigned long constant or a signed
int? */
int count = bitcount(b);
/* is this undefined- trying to send a negative int to bitcount
function? */
推荐答案
G Patel写道：
G Patel wrote:
我想知道如果有人知道以下功能是否能够作为非2s补充机器上的设定位计数器正常工作
（如K& R2暗示的那样）。
| int bitcount（unsigned x）
| {
| int count;
|
| for（count = 0; x！= 0; count ++，x& =（x-1））
| ;
|
|返回计数;
| }
我无法想象为什么这会在1s补码或
sign-mag机器上失败的原因（并且找不到非2s赞美机器来尝试它
上）。就C而言，它是便携式的吗？
机器用什么表示
用于负整数是没有区别的，因为'x''不能是负数！
我发现代码中没有可移植性或一致性问题。
而且，如果我在主程序中声明了一个signed int并且想要将msb设置为1，我可以这样做吗（ 32位整数）：
int b = 0x8000000;
我相信你错过零点。
/ *是0x80000000作为无符号长常数或签名
诠释？ * /
两者都没有：给定32位的假设，常数
（全7个零）将是一个unsigned int。由于此常量的
值对于普通的int而言太大，因此尝试将
转换为int，或者生成实现定义的
结果或引发实现定义的信号。在大多数32位
实现中，`b''将初始化为INT_MIN，-2147483648 -
但标准实际上并不能保证这一点。 />
int count = bitcount（b）;
/ *这是未定义的 - 试图将负int发送给bitcount
函数？ * /
Hi, I''m wondering if anyone knows if the following function will
function properly as a set-bit counter on non 2s complement machines
(as K&R2 implies).
| int bitcount(unsigned x)
| {
| int count;
|
| for(count = 0; x != 0; count++, x &= (x-1))
| ;
|
| return count;
| }
I can''t think of a reason why this would fail on a 1s complement or
sign-mag machine (and can''t find a non 2s compliment machine to try it
on). Is it portable as far as C is concerned?
It makes no difference what representation the machine
uses for negative integers, because `x'' cannot be negative!
I see no portability or conformance problems in the code.
And also, if I declare a signed int in the main program and want to set
the msb to 1, can I do this (32bit ints)?:
int b = 0x8000000;
You''re missing a zero here, I believe.
/* is the 0x80000000 taken as an unsigned long constant or a signed
int? */
Neither: Given the assumption of 32 bits, the constant
(with all seven zeroes) will be an `unsigned int''. Since the
value of this constant is too large for plain `int'', trying to
convert it to `int'' either produces an implementation-defined
result or raises an implementation-defined signal. On most 32-bit
implementations, `b'' will be initialized to INT_MIN, -2147483648 --
but the Standard doesn''t actually guarantee this.
int count = bitcount(b);
/* is this undefined- trying to send a negative int to bitcount
function? */
否：转换为另一种方式，从签名到无签名，
定义明确。但是，转换可能会更改表示中一位的
数。例如，签名幅度计算机上的
表示-1有一个两位
一位。将其转换为unsigned将产生值
UINT_MAX，其至少有十六位。避免这样的惊喜是坚持无符号类型的原因之一
用于比特摆弄。
- -
Eric Sosman
es ***** @ acm-dot-org .inva 盖子
G Patel写道：
G Patel wrote:
我想知道是否有人知道是否以下功能将作为非2s补充机器上的设定位计数器正常工作
（如K& R2所示）。
| int bitcount（unsigned x）
| {
| int count;
|
| for（count = 0; x！= 0; count ++，x& =（x-1））
| ;
|
|返回计数;
| }
Hi, I''m wondering if anyone knows if the following function will
function properly as a set-bit counter on non 2s complement machines
(as K&R2 implies).
| int bitcount(unsigned x)
| {
| int count;
|
| for(count = 0; x != 0; count++, x &= (x-1))
| ;
|
| return count;
| }
是的它会起作用。
下面是32位整数的两个计数器：
int Count（unsigned int w）
{
w =（0x55555555& w）+（0x55555555&（w>> 1））;
w =（0x33333333& w）+（0x33333333&（w>> 2））;
w =（0x0f0f0f0f& w）+（0x0f0f0f0f&（w>> 4） ））;
w =（0x00ff00ff& w）+（0x00ff00ff&（w>> 8））;
w =（0x0000ffff& w）+（0x0000ffff &（w>> 16））;
返回w;
}
/ *略快* /
int Count（unsigned int w）
{
const unsigned int all1 = ~0;
const unsigned int mask1h = all1 / 3<< 1;
const unsigned int mask2l = all1 / 5;
const unsigned int mask4l = all1 / 17;
w - =（mask1h& w）>> 1;
w =（w& mask2l）+（（w>> 2）& mask2l）;
w = w +（w>> 4） &安培; mask4l;
w + = w>> 8;
w + = w>> 16;
返回w& 0xff;
}
gtoomey
Yes it will work.
Heres two counters for 32 bit integers:
int Count (unsigned int w)
{
w = (0x55555555 & w) + (0x55555555 & (w>> 1));
w = (0x33333333 & w) + (0x33333333 & (w>> 2));
w = (0x0f0f0f0f & w) + (0x0f0f0f0f & (w>> 4));
w = (0x00ff00ff & w) + (0x00ff00ff & (w>> 8));
w = (0x0000ffff & w) + (0x0000ffff & (w>>16));
return w;
}
/* slightly faster */
int Count (unsigned int w)
{
const unsigned int all1 = ~0;
const unsigned int mask1h = all1 / 3 << 1;
const unsigned int mask2l = all1 / 5;
const unsigned int mask4l = all1 / 17;
w -= (mask1h & w) >> 1;
w = (w & mask2l) + ((w>>2) & mask2l);
w = w + (w >> 4) & mask4l;
w += w >> 8;
w += w >> 16;
return w & 0xff;
}
gtoomey
Eric Sosman写道：
Eric Sosman wrote:
G Patel写道：
G Patel wrote:
我想知道是否有人知道以下功能是否能正常运行作为非2s上的固定位计数器补充
机器（如K& R2暗示的那样）。
| int bitcount（unsigned x）
| {
| int count;
|
| for（count = 0; x！= 0; count ++，x& =（x-1））
| ;
|
|返回计数;
| }
我无法想象为什么这会在1s补码或
sign-mag机器上失败的原因（并且找不到非2s赞美机器来试试
it on）。就C来说它是否可移植？
Hi, I''m wondering if anyone knows if the following function will
function properly as a set-bit counter on non 2s complement machines (as K&R2 implies).
| int bitcount(unsigned x)
| {
| int count;
|
| for(count = 0; x != 0; count++, x &= (x-1))
| ;
|
| return count;
| }
I can''t think of a reason why this would fail on a 1s complement or
sign-mag machine (and can''t find a non 2s compliment machine to try it on). Is it portable as far as C is concerned?
对于负整数使用的机器代表什么没有区别，因为'x''不能是负数！
It makes no difference what representation the machine
uses for negative integers, because `x'' cannot be negative!
I see no portability or conformance problems in the code.
而且，如果我在主程序中声明一个signed int并想要
将msb设置为1 ，我可以这样做（32位整数）吗？：
int b = 0x8000000;
And also, if I declare a signed int in the main program and want to set the msb to 1, can I do this (32bit ints)?:
int b = 0x8000000;
我相信你错过了零点。 />
You''re missing a zero here, I believe.
/ *是0x80000000作为无符号长常量还是带符号的
int？ * /
/* is the 0x80000000 taken as an unsigned long constant or a signed
int? */
两者都没有：给定32位的假设，常数
（全七个零）将是一个unsigned int。由于此常量的值对于普通的int而言太大，因此尝试将其转换为int会产生实现定义的结果或引发实现定义信号。在大多数32位
实现中，b将初始化为INT_MIN，-2147483648 -
但标准实际上并不能保证这一点。
Neither: Given the assumption of 32 bits, the constant
(with all seven zeroes) will be an `unsigned int''. Since the
value of this constant is too large for plain `int'', trying to
convert it to `int'' either produces an implementation-defined
result or raises an implementation-defined signal. On most 32-bit
implementations, `b'' will be initialized to INT_MIN, -2147483648 --
but the Standard doesn''t actually guarantee this.
谢谢。现在我明白了，我去检查C89草案并发现：
整数常量的类型是相应列表中的第一个
其中它的价值可以代表。 unsuffixed decimal：int，long
int，unsigned long int; unsuffixed octal或hexadecimal：int，unsigned
int，long int，unsigned long int;以字母u或U为后缀：
unsigned int，unsigned long int;后缀为字母l或L：long
int，unsigned long int;后缀为字母u或U和l或L：
unsigned long int。
但我想知道 - 是怎么回事扮演任何一个（负面的
常数）。是 - 常数的一部分或只是常数
，其上带有 - 一元运算符。
如何解释这些常数：
-0xF，-077，-56
未提及 - 在标准中的常量前面。
怎么做 - 影响常数（我想它只需要图片中每个列表中的所有
签名类型）。
[我想知道我的C教科书的作者在想什么当他命名为
时：24小时内自学C ......他们不能再错了。
Thank you. Now I get it, I went and checked the C89 draft and found:
The type of an integer constant is the first of the corresponding list
in which its value can be represented. Unsuffixed decimal: int, long
int, unsigned long int; unsuffixed octal or hexadecimal: int, unsigned
int, long int, unsigned long int; suffixed by the letter u or U:
unsigned int, unsigned long int; suffixed by the letter l or L: long
int, unsigned long int; suffixed by both the letters u or U and l or L:
unsigned long int .
But I''m wondering how the "-" plays into any of this (for negative
constants). Is the "-" part of the constant or is it just the constant
with the - unary operator imparted on it.
How would one explain these constants:
-0xF , -077, -56
No mention of "-" that go in front of constants in the standard. How
does the "-" affect the constant (I imagine it just takes all the
signed types in each list out of the picture).
[I wonder what the authors of my C textbook was thinking when he named
it: Teach yourself C in 24 hours ... they couldn''t be more wrong]
这篇关于用于计算设定位数的功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
