language-agnostic - How can I reverse the ON bits in a byte?

Question

I was reading Joel's book where he was suggesting as interview question:

Write a program to reverse the "ON" bits in a given byte.

I only can think of a solution using C.

Asking here so you can show me how to do in a Non C way (if possible)

score 21 · Accepted Answer

我声称技巧问题。:) 反转所有位意味着触发器，但只有打开的位明确表示：

return 0;

score 14 · Accepted Answer

What specifically does that question mean?

Good question. If reversing the "ON" bits means reversing only the bits that are "ON", then you will always get 0, no matter what the input is. If it means reversing all the bits, i.e. changing all 1s to 0s and all 0s to 1s, which is how I initially read it, then that's just a bitwise NOT, or complement. C-based languages have a complement operator, ~, that does this. For example:

unsigned char b = 102;      /* 0x66, 01100110 */
unsigned char reverse = ~b; /* 0x99, 10011001 */

score 4 · Accepted Answer

What specifically does that question mean?

Does reverse mean setting 1's to 0's and vice versa?

Or does it mean 00001100 --> 00110000 where you reverse their order in the byte? Or perhaps just reversing the part that is from the first 1 to the last 1? ie. 00110101 --> 00101011?

Assuming it means reversing the bit order in the whole byte, here's an x86 assembler version:

; 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

not the most optimal solution, a table lookup is faster.

score 4 · Accepted Answer

Reversing the order of bits in 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;
}

I'm sure there are more clever ways of doing it but in that precise case, the interview question is meant to determine if you know bitwise operations so I guess this solution would work.

In an interview, the interviewer usually wants to know how you find a solution, what are you problem solving skills, if it's clean or if it's a hack. So don't come up with too much of a clever solution because that will probably mean you found it somewhere on the Internet beforehand. Don't try to fake that you don't know it neither and that you just come up with the answer because you are a genius, this is will be even worst if she figures out since you are basically lying.

score 3 · Accepted Answer

我可能记错了，但我认为 Joel 的问题是关于计算“on”位而不是反转它们。

干得好：

#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;
}

score 3 · Accepted Answer

If you're talking about switching 1's to 0's and 0's to 1's, using Ruby:

n = 0b11001100
~n

If you mean reverse the order:

n = 0b11001100
eval("0b" + n.to_s(2).reverse)

If you mean counting the on bits, as mentioned by another user:

n = 123
count = 0
0.upto(8) { |i| count = count + n[i] }

♥ Ruby

score 2 · Accepted Answer

这是一个直接从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;
}

score 2 · Accepted Answer

The classic Bit Hacks page has several (really very clever) ways to do this, but it's all in C. Any language derived from C syntax (notably Java) will likely have similar methods. I'm sure we'll get some Haskell versions in this thread ;)

score 2 · Accepted Answer

byte ReverseByte(byte b) { return b ^ 0xff; }

That works if ^ is XOR in your language, but not if it's AND, which it often is.

score 2 · Accepted Answer

2

伪代码..

while (Read())
  Write(0);

于 2009-08-15T21:29:21.820 回答

score 1 · Accepted Answer

1

我可能记错了，但我认为 Joel 的问题是关于计算“on”位而不是反转它们。

于 2008-08-13T17:57:13.243 回答

score 1 · Accepted Answer

这是用于补充位的强制性 Haskell 解决方案，它使用库函数补码：

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)]

score 1 · Accepted Answer

I'd modify palmsey's second example, eliminating a bug and eliminating the eval:

n = 0b11001100
n.to_s(2).rjust(8, '0').reverse.to_i(2)

The rjust is important if the number to be bitwise-reversed is a fixed-length bit field -- without it, the reverse of 0b00101010 would be 0b10101 rather than the correct 0b01010100. (Obviously, the 8 should be replaced with the length in question.) I just got tripped up by this one.

score 1 · Accepted Answer

如果问题意味着翻转所有位，并且不允许使用类似 C 的运算符，例如 XOR 和 NOT，那么这将起作用：

bFlipped = -1 - bInput;

score 1 · Accepted Answer

在这里询问，以便您可以向我展示如何以非 C 方式进行操作（如果可能）

假设您有数字 10101010。要将 1 更改为 0（反之亦然），您只需使用 XOR：

 10101010
^11111111
 --------
 01010101

用手做这件事就像你会得到的那样“非C”。

然而，从问题的措辞来看，它听起来真的只是关闭“ON”位......在这种情况下，答案为零（正如已经提到的）（当然，除非问题实际上是要求交换位）。

score 0 · Accepted Answer

Reversing the bits. For example we have a number represented by 01101011 . Now if we reverse the bits then this number will become 11010110. Now to achieve this you should first know how to do swap two bits in a number. Swapping two bits in a number:- XOR both the bits with one and see if results are different. If they are not then both the bits are same otherwise XOR both the bits with XOR and save it in its original number; Now for reversing the number FOR I less than Numberofbits/2 swap(Number,I,NumberOfBits-1-I);

score 0 · Accepted Answer

由于该问题要求采用非 C 方式，因此这是一个 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);
}

language-agnostic - How can I reverse the ON bits in a byte?

17 回答 17

Related

Reference