如何反转字节中的ON位？
我正在阅读乔尔的书，他在这本书中建议作为面试问题：
Write a program to reverse the "ON" bits in a given byte.
我只能想到使用C的解决方案。
问这里，以便我们可以向我展示如何以非C方式进行操作(如果可能)
解决方案
回答
这个问题具体是什么意思？
反向表示将1设置为0，反之亦然吗？
还是说00001100-> 00110000，我们在其中反转了字节顺序？还是只是反转从前1个到最后1个的部分？ IE。 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
不是最佳解决方案，表查找速度更快。
回答
反转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;
}
我敢肯定有更多聪明的方法可以做到这一点，但在那种确切的情况下，面试问题是要确定我们是否知道按位运算，所以我猜想这种解决方案会起作用。
在面试中，面试官通常想知道我们如何找到解决方案，我们解决问题的技能是什么，无论是干净的还是黑手。因此，不要提出太多聪明的解决方案，因为这可能意味着我们事先在Internet上找到了它。不要因为自己是天才而假装不知道也不知道，而只是想出答案，如果她弄清楚了，因为你基本上是在撒谎，这甚至会更糟。
回答
经典的Bit Hacks页面有几种(确实非常聪明)的方法来做到这一点，但都是用C编写的。任何从C语法派生的语言(特别是Java)都可能具有相似的方法。我确定我们会在该线程中获得一些Haskell版本;)
回答
byte ReverseByte(byte b)
{
return b ^ 0xff;
}
如果^在语言中是XOR，那是可行的，但是如果它是AND(通常是这样)，则无效。
回答
What specifically does that question mean?
好问题。如果反转" ON"位意味着仅反转" ON"位，那么无论输入是什么，我们始终将得到0。如果这意味着反转所有位，即将所有1都更改为0并将所有0都更改为1，这就是我最初的读取方式，那么这只是按位NOT或者补码。基于C的语言具有补码运算符〜，可以执行此操作。例如：
unsigned char b = 102; /* 0x66, 01100110 */ unsigned char reverse = ~b; /* 0x99, 10011001 */
回答
如果我们要谈论的是使用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] }
？红宝石
回答
我可能记错了，但是我认为Joel的问题是关于计数"接通"位而不是反转它们。
回答
由于该问题要求使用非C方式，因此以下是SLIB的Scheme实施，它被SLIB窃：
(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);
}
回答
这是直接从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;
}
回答
I'm probably misremembering, but I thought that Joel's question was about counting the "on" bits rather than reversing them.
干得好：
#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;
}
回答
这是用于补充位的必填Haskell soln，它使用库函数complement：
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)]
回答
我将修改palmsey的第二个示例，消除一个错误并消除eval：
n = 0b11001100 n.to_s(2).rjust(8, '0').reverse.to_i(2)
如果要按位反转的数字是固定长度的位字段，则"正确"很重要-没有它，则" 0b00101010"的反转将是" 0b10101"而不是正确的" 0b01010100"。 (很明显，应该将8替换为有问题的长度。)我只是被这个绊倒了。
回答
如果问题是要翻转所有位，并且不允许我们使用类似C的运算符(例如XOR和NOT)，那么它将起作用：
bFlipped = -1 - bInput;
回答
我要求技巧问题。 :)将所有位取反意味着一个触发器，但是只有清楚的位才意味着：
return 0;
回答
伪代码..
while (Read()) Write(0);
回答
Asking here so you can show me how to do in a Non C way (if possible)
假设号码是10101010. 要将1s更改为0(反之亦然)，只需使用XOR：
10101010 ^11111111 -------- 01010101
手工完成的过程与我们将获得的" Non C"差不多。
但是，从问题的措辞看来，这听起来好像只是在关闭" ON"位...在这种情况下，答案为零(如前所述)(当然，问题实际上是要求交换顺序)位)。
