C の unsigned char で 1 の数を返す C コードが必要です。明らかでない場合、なぜそれが機能するのかについて説明が必要です。32 ビットの数値のコードはたくさん見つかりましたが、unsigned char のコードはあまり見つかりませんでした。
29303 次
8 に答える
20
const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
unsigned char CountOnes(unsigned char x)
{
unsigned char results;
results = oneBits[x&0x0f];
results += oneBits[x>>4];
return results
}
0 から 15 までのビット数を知る配列を用意します。各ニブルの結果を追加します。
于 2009-03-30T17:07:42.437 に答える
15
unsigned char に対しても同じコードが機能します。それらをテストするすべてのビットをループします。これを参照してください。
于 2009-03-30T16:42:35.070 に答える
7
HACKMEMには、このアルゴリズムが 3 つの操作で含まれています (大まかに C に翻訳されています)。
bits = (c * 01001001001ULL & 042104210421ULL) % 017;
(ULLは 64 ビット演算を強制するためのものです。必要なのは、かろうじて... この計算には 33 ビット整数が必要です。)
実際には、8 ビットしかカウントしていないため、2 番目の定数を に置き換えることができますが、042104210021ULL見た目は対称的ではありません。
これはどのように作動しますか？cビットごとに考えて(a + b) % c = (a % c + b % c) % c、 、 、 および(a | b) == a + biffを覚えておいて(a & b) == 0ください。
(c * 01001001001ULL & 042104210421ULL) % 017
01 01001001001 01 1
02 02002002002 02000000000 1
04 04004004004 04000000 1
010 010010010010 010000 1
020 020020020020 020 1
040 040040040040 040000000000 1 # 040000000000 == 2 ** 32
0100 0100100100100 0100000000 1
0200 0200200200200 0200000 1
64 ビットの算術演算が利用できない場合は、cニブルに分割し、各半分を実行して 9 回の演算を行うことができます。これには 13 ビットしか必要ないため、16 ビットまたは 32 ビットの演算を使用しても機能します。
bits = ((c & 017) * 0421 & 0111) % 7 + ((c >> 4) * 0421 & 0111) % 7;
(c * 0421 & 01111) % 7
1 0421 01 1
2 01042 01000 1
4 02104 0100 1
8 04210 010 1
たとえばc == 105 == 0b11001001、
c == 0100
| 040
| 010
| 01 == 0151
* 01001001001001ULL == 0100100100100
| 040040040040
| 010010010010
| 01001001001 == 0151151151151
& 0421042104210421ULL == 0100000000
| 04000000000
| 010000
| 01 == 04100010001
% 017 == 4
c & 017 == 8 | 1 == 011
011 * 0421 == 8 * 0421 | 1 * 0421 == 04210 | 0421 == 04631
04631 & 0111 == 04210 & 0111 | 0421 & 0111 == 010 | 01 == 011
011 % 7 == 2
c >> 4 == 4 | 2 == 06
06 * 0421 == 4 * 0421 | 2 * 0421 == 02104 | 01042 == 03146
03146 & 0111 == 02104 & 0111 | 01042 & 0111 == 0100 | 01000 == 01100
01100 % 7 == 2
2 + 2 == 4
于 2009-03-30T17:28:05.103 に答える
5
少しいじるハックのページを参照してください: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
これには多くの優れたソリューションがあります。
また、この関数は、最も単純な実装ではかなり簡単です。これを行う方法を学ぶために時間をかける必要があります。
于 2009-03-30T16:42:35.837 に答える
3
unsigned char と同じくらい小さい整数の場合、小さなルックアップ テーブルを使用して最高のパフォーマンスを得ることができます。
あなたが言及している人口カウントアルゴリズムは知っています。それらは、レジスタに格納された整数よりも小さい複数のワードの演算を行うことによって機能します。
この手法は SWAR ( http://en.wikipedia.org/wiki/SWAR ) と呼ばれます。
詳細については、ハッカーズ デライトの Web サイト (www.hackersdelight.org) を確認することをお勧めします。彼はサンプル コードを持っており、これらのトリックを詳細に説明する本を書いています。
于 2009-03-30T16:43:19.967 に答える
0
すでに回答したように、ビットをカウントする標準的な方法は、符号なし文字でも機能します。
例：
unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
if ( value & 1 == 1 )
bitCount++;
value >>= 1;
}
于 2009-03-30T16:50:53.977 に答える
-1
unsigned char は、32 ビットの浮動小数点数または整数が「数値」であるのとまったく同じように「数値」です。
char をそのビットとして描く場合:
01010011 (8 ビット);
次のようにして、設定されたビットをカウントできます。
値を取り、x と言って x % 2 を取ると、残りは 1 または 0 になります。つまり、char のエンディアンに応じて、左端または右端のビットになります。残りを別の変数に累積します (これは結果として設定されたビット数になります)。
次に >> (右シフト) 1 ビット。
8 ビットがシフトされるまで繰り返します。
Cコードは、私の疑似コードから実装するのはかなり簡単なはずですが、基本的には
public static int CountSetBits(char c)
{
int x = 0;
int setBits = 0;
while (x < 7)
{
setBits = setBits + c % 2;
c = c >> 1;
x = x + 1;
}
}
于 2009-03-30T16:43:56.143 に答える
-1
Ephemient の投稿に基づいて、分岐のない 8 ビット バージョンがあります。16進表記です。
typedef unsigned char UINT8;
typedef unsigned short UINT16;
typedef unsigned long long UINT64;
int hammingWeight8( const UINT8& c)
{
return ( c* 0x8040201ULL & 0x11111111)%0xF;
}
それを 2 回適用すると、9 回の操作が必要な 16 ビット バージョンがあります。
int hammingWeight16( const UINT16& c)
{
return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF +
((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}
ここでは、64 ビットのレジスタと 11 の操作を必要とするバリアントの 16 ビット バージョンを作成します。前のものよりも良くないように見えますが、1 つのモジュロ演算を使用するだけです。
int hammingWeight16( const UINT16& c)
{
UINT64 w;
w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
return (c!=0)*(w+1+(c==0xFFFF)*15);
}
于 2016-03-15T19:29:15.510 に答える