0 から 2 n -1 までカウントするアルゴリズムを見つけようとしていますが、ビット パターンが逆になっています。単語の n LSB だけを気にします。ご想像のとおり、私は失敗しました。
n=3 の場合:
000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7
あなたはアイデアを得る。
疑似コードでの回答は素晴らしいです。任意の言語のコード フラグメントを歓迎します。ビット操作のない回答が優先されます。
簡単な説明やソースへのポインタさえもなしに断片を投稿しないでください。
編集：追加するのを忘れていました。カウント変数をビット反転する単純な実装が既にあります。ある意味で、この方法は実際にはカウントされていません。
これは、ビット操作で最も簡単だと思いますが、これは好まれませんでした
32 ビットの int を想定すると、32 の手順を実行せずにすべてのビットを反転できる気の利いたコードのチャンクを次に示します。
unsigned int i;
i = (i & 0x55555555) << 1 | (i & 0xaaaaaaaa) >> 1;
i = (i & 0x33333333) << 2 | (i & 0xcccccccc) >> 2;
i = (i & 0x0f0f0f0f) << 4 | (i & 0xf0f0f0f0) >> 4;
i = (i & 0x00ff00ff) << 8 | (i & 0xff00ff00) >> 8;
i = (i & 0x0000ffff) << 16 | (i & 0xffff0000) >> 16;
i >>= (32 - n);
基本的に、これはすべてのビットのインターリーブ シャッフルを行います。毎回、値の約半分のビットが残りの半分と交換されます。
最後の行は、ビン「n」が最上位ビットになるようにビットを再調整するために必要です。
"n" が <= 16 または <= 8 の場合、これの短いバージョンが可能です。
このソリューションは、元は 2 進数であり、要求者が指定したように従来の数学に変換されました。
少なくとも 2 による乗算と 2 による除算は、速度のために << 1 および >> 1 である必要があります。加算と減算は、おそらくいずれにせよ重要ではありません。
nBits の代わりに mask を渡し、乗算または除算の代わりにビットシフトを使用し、末尾再帰をループに変更すると、他のすべての呼び出しは単一の呼び出しにすぎないため、これがおそらく最もパフォーマンスの高いソリューションになります。追加すると、Alnitak のソリューションと同じくらい遅くなるだけで、4 回、場合によっては 8 回の呼び出しに 1 回しかかかりません。
int incrementBizarre(int initial, int nBits)
// in the 3 bit example, this should create 100
mask=2^(nBits-1)
// This should only return true if the first (least significant) bit is not set
// if initial is 011 and mask is 100
// 3 4, bit is not set
if(initial < mask)
// If it was not, just set it and bail.
return initial+ mask // 011 (3) + 100 (4) = 111 (7)
else
// it was set, are we at the most significant bit yet?
// mask 100 (4) / 2 = 010 (2), 001/2 = 0 indicating overflow
if(mask / 2) > 0
// No, we were't, so unset it (initial-mask) and increment the next bit
return incrementBizarre(initial - mask, mask/2)
else
// Whoops we were at the most significant bit. Error condition
throw new OverflowedMyBitsException()
うわー、それはちょっとクールになりました。私は最後の1秒まで再帰を理解していませんでした。
それは間違っているように感じます-動作しないはずの操作がいくつかあるように感じますが、あなたがしていることの性質のために動作します(少し左にいくつかのビットを操作しているときに問題が発生する必要があるように感じます)はゼロではありませんが、左側のすべてのビットがゼロでない限り、ビットを操作することはできません。これは非常に奇妙な条件ですが、本当です。
110 から 001 に取得するフローの例 (後方 3 から後方 4):
mask 100 (4), initial 110 (6); initial < mask=false; initial-mask = 010 (2), now try on the next bit
mask 010 (2), initial 010 (2); initial < mask=false; initial-mask = 000 (0), now inc the next bit
mask 001 (1), initial 000 (0); initial < mask=true; initial + mask = 001--correct answer
各ステップで、値の左端の 0 桁を見つけます。それを設定し、その左側のすべての桁をクリアします。数字の 0 が見つからない場合は、オーバーフローしています。0 を返すか、停止するか、クラッシュするか、または必要なものは何でもかまいません。
これは、通常のバイナリ インクリメントで発生することです (これは、ハードウェアでの実装方法ではなく、効果であることを意味します) が、右側ではなく左側で実行しています。
これをビット演算、文字列などで行うかどうかは、あなた次第です。bitops で実行する場合は、clz (または同等の hibit スタイルの関数への呼び出し)~valueが最も効率的な方法である可能性があります: __builtin_clz (使用可能な場合)。しかし、それは実装の詳細です。
void reverse(int nMaxVal, int nBits)
{
int thisVal, bit, out;
// Calculate for each value from 0 to nMaxVal.
for (thisVal=0; thisVal<=nMaxVal; ++thisVal)
{
out = 0;
// Shift each bit from thisVal into out, in reverse order.
for (bit=0; bit<nBits; ++bit)
out = (out<<1) + ((thisVal>>bit) & 1)
}
printf("%d -> %d\n", thisVal, out);
}
これがPerlでの答えです。すべてが 1 のパターンの後に何が来るかは言わないので、0 を返します。別の言語に簡単に翻訳できるように、ビットごとの操作を取り出しました。
sub reverse_increment {
my($n, $bits) = @_;
my $carry = 2**$bits;
while($carry > 1) {
$carry /= 2;
if($carry > $n) {
return $carry + $n;
} else {
$n -= $carry;
}
}
return 0;
}
逆にすると、ビットパターンが逆になり、シーケンス0 to 2^n-1全体をほぼカバーします0-2^n-1
Sum = 2^n * (2^n+1)/2
O(1)手術。ビット反転を行う必要はありません
必要に応じて、最上位ビットに 1 を追加してから、次の (下位の) ビットに繰り越します。バイトを操作することで、これを高速化できます。
たぶん、0 から N にインクリメントし (「通常の」方法)、繰り返しごとに ReverseBitOrder() を実行します。ここでいくつかの実装を見つけることができます(私は LUT が一番好きです)。本当に速いはずです。
これは、実際には加算を行わないソリューションですが、シーケンスのオン/オフ パターン (ほとんどのシグ ビットが毎回交互に、次の最も大きなシグ ビットが 1 回おきに交互になるなど) を利用し、必要に応じて n を調整します。
#define FLIP(x, i) do { (x) ^= (1 << (i)); } while(0)
int main() {
int n = 3;
int max = (1 << n);
int x = 0;
for(int i = 1; i <= max; ++i) {
std::cout << x << std::endl;
/* if n == 3, this next part is functionally equivalent to this:
*
* if((i % 1) == 0) FLIP(x, n - 1);
* if((i % 2) == 0) FLIP(x, n - 2);
* if((i % 4) == 0) FLIP(x, n - 3);
*/
for(int j = 0; j < n; ++j) {
if((i % (1 << j)) == 0) FLIP(x, n - (j + 1));
}
}
}
n を 2 の累乗、x をステップ実行する変数として使用します。
(defun inv-step (x n) ; the following is a function declaration
"returns a bit-inverse step of x, bounded by 2^n" ; documentation
(do ((i (expt 2 (- n 1)) ; loop, init of i
(/ i 2)) ; stepping of i
(s x)) ; init of s as x
((not (integerp i)) ; breaking condition
s) ; returned value if all bits are 1 (is 0 then)
(if (< s i) ; the loop's body: if s < i
(return-from inv-step (+ s i)) ; -> add i to s and return the result
(decf s i)))) ; else: reduce s by i
この構文に慣れていない可能性があるため、徹底的にコメントしました。
編集：これは末尾再帰バージョンです。テールコール最適化を備えたコンパイラがあれば、少し速いようです。
(defun inv-step (x n)
(let ((i (expt 2 (- n 1))))
(cond ((= n 1)
(if (zerop x) 1 0)) ; this is really (logxor x 1)
((< x i)
(+ x i))
(t
(inv-step (- x i) (- n 1))))))