Как я могу инвертировать НА битах в байте?

Начиная с вопроса, который задают для non-C пути, вот реализация Схемы, бодро незаконно заимствуемая от 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 (для людей, незнакомых со Схемой), это выглядело бы примерно так (с пониманием, что в Схеме, числа могут быть произвольно большими):

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

Вот обязательный Haskell soln для дополнения битов, оно использует библиотечную функцию, дополнение:

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

Я, вероятно, misremembering, но я думал, что вопрос Joel был о подсчете "на" битах вместо того, чтобы инвертировать их.

И вот версия, непосредственно вырезанная и вставленная от OpenJDK, который интересен, потому что это не включает цикла. С другой стороны, в отличие от версии Схемы я отправил, эта версия только работает на 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;
}

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

Это работает если ^ XOR на Вашем языке, но не, если это AND, который это часто.

Классическая страница Bit Hacks имеет несколько (действительно очень умных) способов сделать это, но это - все в C. Любой язык, полученный из синтаксиса C (особенно Java), будет, вероятно, иметь похожие методы. Я уверен, что мы получим некоторые версии Haskell в этом потоке ;)

Я, вероятно, misremembering, но я думал, что вопрос 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;
}

Если Вы говорите о переключении 1 к 0 и 0 к 1's, с помощью Ruby:

n = 0b11001100
~n

Если Вы имеете в виду реверс порядок:

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

Если Вы означаете рассчитывать на биты, как упомянуто другим пользователем:

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

♥ Ruby

Инвертирование порядка битов в 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;
}

Я уверен, что существуют более умные способы сделать его, но в том точном случае, вопрос об интервью предназначен, чтобы определить, знаете ли Вы битовые операции, таким образом, я предполагаю, что это решение работало бы.

В интервью интервьюер обычно хочет знать, как Вы находите решение, что является Вами навыки решения проблем, если это чисто или если это - взлом. Не предлагайте слишком много умного решения, потому что это будет, вероятно, означать нахождение его где-нибудь в Интернете заранее. Не пытайтесь фальсифицировать это, Вы не знаете это ни один и что Вы просто придумываете ответ, потому что Вы - гений, это, будет даже худшим, если она выяснит, так как Вы в основном лежите.

Что конкретно, что вопрос означает?

Реверс значит установку 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

не наиболее оптимальное решение, поиск по таблице быстрее.

Что конкретно, что вопрос означает?

Хороший вопрос. Если инвертирование "НА" битах означает инвертировать только биты, которые "ВКЛЮЧЕНЫ", затем Вы будете всегда добираться 0, каков вход. Если это означает инвертировать все биты, т.е. изменять всю 1 с на 0s и весь 0s к 1 с, которая является, как я первоначально считал его, то это - просто битовое "НЕ" или дополнение. Языки на базе С имеют дополнительный оператор, ~, это делает это. Например:

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

Я задаю вопрос с подвохом. :) Обращение всех битов означает триггер, но только те биты, которые явно включены, означают:

return 0;

Задавая здесь вопрос, вы можете показать мне, как делать не C способом (если возможно)

Скажем, у вас есть номер 10101010. Чтобы изменить единицы на нули (и наоборот наоборот) вы просто используете XOR:

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

Выполнение этого вручную - это примерно столько же "Non C", сколько вы получите.

Однако из формулировки вопроса действительно звучит так, как будто это только поворот выключены биты "ВКЛ" ... В этом случае ответ равен нулю (как уже упоминалось) (если, конечно, вопрос действительно не просит поменять порядок битов).

Я бы изменил второй пример Палмси, устранив ошибку и устранив eval :

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

rjust важно, если число должно быть Побитовое обращение - это битовое поле фиксированной длины - без него обратное 0b00101010 было бы 0b10101 , а не правильным 0b01010100 . (Очевидно, 8 следует заменить на указанную длину.) Я просто сбился с пути из-за этого.

Если вопрос означает перевернуть все биты, и вам не разрешено использовать C-подобные операторы, такие как XOR и NOT, тогда это будет работать:

bFlipped = -1 - bInput;

псевдокод ..

while (Read())
  Write(0);