私はジョエルの本を読んでいて、彼がインタビューの質問として提案していた:
特定のバイトの「ON」ビットを逆にするプログラムを作成します。
Cを使用した解決策しか思い浮かびません。
C以外の方法で行う方法を教えてくれるように、ここで質問します（可能であれば）
7838 次
17 に答える
21
私はひっかけ問題を主張します。:) すべてのビットを逆にすることはフリップフロップを意味しますが、明らかにオンになっているビットのみが次のことを意味します。
return 0;
于 2009-08-15T21:13:29.450 に答える
14
その質問は具体的にどういう意味ですか？
良い質問。「ON」ビットを反転することが「ON」のビットのみを反転することを意味する場合、入力が何であれ、常に 0 になります。それがすべてのビットを逆にすることを意味する場合、つまり、すべての 1 を 0 に、すべての 0 を 1 に変更することを意味する場合、これは私が最初に読んだ方法であり、ビット単位の NOT または補数です。C ベースの言語には、~これを行う補数演算子 があります。例えば：
unsigned char b = 102; /* 0x66, 01100110 */
unsigned char reverse = ~b; /* 0x99, 10011001 */
于 2008-08-13T14:44:10.780 に答える
4
その質問は具体的にどういう意味ですか？
リバースとは、1 を 0 に、またはその逆に設定することを意味しますか?
それとも、00001100 --> 00110000という意味で、バイト内で順序を逆にしますか? それとも、最初の 1 から最後の 1 までの部分を逆にするだけですか? すなわち。00110101 --> 00101011 ?
バイト全体のビット順序を逆にすることを意味すると仮定すると、x86 アセンブラー バージョンは次のようになります。
; al is input register
; bl is output register
xor bl, bl ; clear output
; first bit
rcl al, 1 ; rotate al through carry
rcr bl, 1 ; rotate carry into bl
; duplicate above 2-line statements 7 more times for the other bits
最適なソリューションではありませんが、テーブル ルックアップの方が高速です。
于 2008-08-13T13:03:17.253 に答える
4
C# でビットの順序を逆にする:
byte ReverseByte(byte b)
{
byte r = 0;
for(int i=0; i<8; i++)
{
int mask = 1 << i;
int bit = (b & mask) >> i;
int reversedMask = bit << (7 - i);
r |= (byte)reversedMask;
}
return r;
}
もっと巧妙な方法があると確信していますが、その正確な場合、インタビューの質問は、ビット単位の操作を知っているかどうかを判断することを目的としているため、この解決策が機能すると思います.
面接では、面接担当者は通常、解決策をどのように見つけたか、問題解決スキルは何か、それがクリーンなのかハックなのかを知りたがります。したがって、あまりにも多くの巧妙な解決策を考え出さないでください。それはおそらく、事前にインターネット上のどこかで見つけたことを意味するからです。あなたもそれを知らない、そしてあなたは天才だから答えを思いついたというふりをしないでください。
于 2008-08-13T13:04:59.433 に答える
3
Ruby を使用して、1 を 0 に、0 を 1 に切り替えることについて話している場合:
n = 0b11001100
~n
順序を逆にする場合：
n = 0b11001100
eval("0b" + n.to_s(2).reverse)
別のユーザーが述べたように、オンビットをカウントする場合：
n = 123
count = 0
0.upto(8) { |i| count = count + n[i] }
♥ ルビー
于 2008-08-13T15:11:45.810 に答える
3
私の記憶違いかもしれませんが、Joel の質問は、「オン」のビットを逆にするのではなく、数を数えることに関するものだと思いました。
どうぞ：
#include <stdio.h>
int countBits(unsigned char byte);
int main(){
FILE* out = fopen( "bitcount.c" ,"w");
int i;
fprintf(out, "#include <stdio.h>\n#include <stdlib.h>\n#include <time.h>\n\n");
fprintf(out, "int bitcount[256] = {");
for(i=0;i<256;i++){
fprintf(out, "%i", countBits((unsigned char)i));
if( i < 255 ) fprintf(out, ", ");
}
fprintf(out, "};\n\n");
fprintf(out, "int main(){\n");
fprintf(out, "srand ( time(NULL) );\n");
fprintf(out, "\tint num = rand() %% 256;\n");
fprintf(out, "\tprintf(\"The byte %%i has %%i bits set to ON.\\n\", num, bitcount[num]);\n");
fprintf(out, "\treturn 0;\n");
fprintf(out, "}\n");
fclose(out);
return 0;
}
int countBits(unsigned char byte){
unsigned char mask = 1;
int count = 0;
while(mask){
if( mask&byte ) count++;
mask <<= 1;
}
return count;
}
于 2008-08-14T17:48:17.627 に答える
2
そして、これがOpenJDKから直接カットアンドペーストされたバージョンです。これは、ループが含まれていないので興味深いものです。一方、私が投稿したSchemeバージョンとは異なり、このバージョンは32ビットと64ビットの数値でのみ機能します。:-)
32ビットバージョン：
public static int reverse(int i) {
// HD, Figure 7-1
i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
i = (i << 24) | ((i & 0xff00) << 8) |
((i >>> 8) & 0xff00) | (i >>> 24);
return i;
}
64ビットバージョン：
public static long reverse(long i) {
// HD, Figure 7-1
i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;
i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;
i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;
i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;
i = (i << 48) | ((i & 0xffff0000L) << 16) |
((i >>> 16) & 0xffff0000L) | (i >>> 48);
return i;
}
于 2008-08-14T01:43:01.493 に答える
2
古典的なBit Hacksページには、これを行うための (非常に巧妙な) 方法がいくつかありますが、すべて C で記述されています。C 構文から派生した言語 (特に Java) には、同様の方法がある可能性があります。このスレッドでいくつかの Haskell バージョンを入手できると確信しています ;)
于 2008-08-13T13:05:31.400 に答える
2
byte ReverseByte(byte b) { return b ^ 0xff; }
^あなたの言語で が XOR の場合は機能しますが、 の場合は機能しませんAND。これはよくあることです。
于 2008-08-13T13:15:42.393 に答える
1
これがビットを補完するための必須のHaskellsolnであり、ライブラリ関数complimentを使用します。
import Data.Bits
import Data.Int
i = 123::Int
i32 = 123::Int32
i64 = 123::Int64
var2 = 123::Integer
test1 = sho i
test2 = sho i32
test3 = sho i64
test4 = sho var2 -- Exception
sho i = putStrLn $ showBits i ++ "\n" ++ (showBits $complement i)
showBits v = concatMap f (showBits2 v) where
f False = "0"
f True = "1"
showBits2 v = map (testBit v) [0..(bitSize v - 1)]
于 2008-09-24T00:51:51.847 に答える
1
私はおそらく覚えていませんが、ジョエルの質問は「オン」ビットを逆にするのではなく、数えることだと思いました。
于 2008-08-13T17:57:13.243 に答える
1
Palmsey の 2 番目の例を変更して、バグを排除し、以下を排除しevalます。
n = 0b11001100
n.to_s(2).rjust(8, '0').reverse.to_i(2)
rjustビットごとに反転される数値が固定長のビット フィールドである場合、0b00101010は0b10101重要です0b01010100。(明らかに、8 は問題の長さに置き換える必要があります。) 私はこれにつまずきました。
于 2009-08-15T20:16:18.473 に答える
1
C以外の方法で行う方法を教えてくれるように、ここで質問します（可能であれば）
番号が 10101010 だとします。1 を 0 に (またはその逆に) 変更するには、XOR を使用します。
10101010
^11111111
--------
01010101
手作業で行うのは、「非 C」とほぼ同じです。
ただし、質問の文言からは、「ON」ビットのみをオフにしているように聞こえます...その場合、答えはゼロです（すでに述べたように）（もちろん、質問が実際に順序を入れ替えることを求めている場合を除きます）ビット）。
于 2009-08-15T22:00:20.243 に答える
1
質問がすべてのビットを反転することを意味し、XOR や NOT などの C ライクな演算子の使用が許可されていない場合、これは機能します。
bFlipped = -1 - bInput;
于 2009-08-15T20:52:06.497 に答える
0
質問は非Cの方法を求めていたので、SLIBから元気に盗聴されたSchemeの実装を次に示します。
(define (bit-reverse k n)
(do ((m (if (negative? n) (lognot n) n) (arithmetic-shift m -1))
(k (+ -1 k) (+ -1 k))
(rvs 0 (logior (arithmetic-shift rvs 1) (logand 1 m))))
((negative? k) (if (negative? n) (lognot rvs) rvs))))
(define (reverse-bit-field n start end)
(define width (- end start))
(let ((mask (lognot (ash -1 width))))
(define zn (logand mask (arithmetic-shift n (- start))))
(logior (arithmetic-shift (bit-reverse width zn) start)
(logand (lognot (ash mask start)) n))))
C（Schemeに慣れていない人向け）として書き直されると、次のようになります（Schemeでは、数値は任意に大きくなる可能性があることを理解しています）。
int
bit_reverse(int k, int n)
{
int m = n < 0 ? ~n : n;
int rvs = 0;
while (--k >= 0) {
rvs = (rvs << 1) | (m & 1);
m >>= 1;
}
return n < 0 ? ~rvs : rvs;
}
int
reverse_bit_field(int n, int start, int end)
{
int width = end - start;
int mask = ~(-1 << width);
int zn = mask & (n >> start);
return (bit_reverse(width, zn) << start) | (~(mask << start) & n);
}
于 2008-08-14T01:35:32.260 に答える
0
ビットを反転します。たとえば、 01101011 で表される数値があります。ここで、ビットを逆にすると、この数値は 11010110 になります。これを実現するには、まず数値の 2 ビットをスワップする方法を知っておく必要があります。数値の 2 つのビットを交換する:- 両方のビットを 1 で XOR し、結果が異なるかどうかを確認します。そうでない場合は、両方のビットが同じです。それ以外の場合は、両方のビットを XOR で XOR し、元の番号で保存します。ここで、Numberofbits/2 未満の FOR I を反転します swap(Number,I,NumberOfBits-1-I);
于 2013-07-29T04:02:19.390 に答える