Как я могу обратить биты ON в байте?

Я читал книгу Джоэла, где он предлагал в качестве вопроса для интервью:

Напишите программу для обращения битов «ON» в данном байте.

Я могу только думать о решении, используя C.

Спросите здесь, чтобы вы могли показать мне, как это сделать не на C (если это возможно)

13.08.2008 13:00:48
XOR против всех 1с.
Brad Wilson 24.09.2008 01:01:01
17 ОТВЕТОВ

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

Означает ли обратное значение установки 1 в 0 и наоборот?

Или это означает 00001100 -> 00110000, где вы меняете их порядок в байтах? Или, может быть, просто поменять местами часть от первой до последней? то есть. 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

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

4
13.08.2008 13:20:55

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

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

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

4
13.08.2008 13:22:02

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

2
13.08.2008 13:05:31

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

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

2
13.08.2008 13:15:42

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

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

unsigned char b = 102;      /* 0x66, 01100110 */
unsigned char reverse = ~b; /* 0x99, 10011001 */
14
13.08.2008 14:44:10

Если вы говорите о переключении 1 на 0 и 0 на 1, используя 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] }

♥ Рубин

3
13.08.2008 18:04:03

Я, вероятно, неправильно помню, но я подумал, что вопрос Джоэла был в том, чтобы считать биты « включено», а не поменять их местами .

1
13.08.2008 17:57:13

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

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);
}
0
14.08.2008 01:35:32

А вот версия, прямо вырезанная и вставленная из 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;
}
2
14.08.2008 01:43:01

Я, вероятно, неправильно помню, но я подумал, что вопрос Джоэла был в том, чтобы считать биты «включено», а не поменять их местами.

Ну вот:

#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;
}
3
14.08.2008 17:48:17

Вот обязательный алгоритм 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)]
1
24.09.2008 01:40:33

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

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

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

1
15.08.2009 21:15:04

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

bFlipped = -1 - bInput;
1
15.08.2009 20:52:06

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

return 0;
21
15.08.2009 21:13:29

псевдокод ..

while (Read())
  Write(0);
2
15.08.2009 21:29:21

Спросите здесь, чтобы вы могли показать мне, как это сделать не на C (если это возможно)

Допустим, у вас есть номер 10101010. Чтобы изменить 1 с на 0 (и наоборот), вы просто используете XOR:

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

Делать это вручную - это не так "Non C", как вы получите.

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

1
15.08.2009 22:00:20

Поменять местами Например, у нас есть номер, представленный 01101011. Теперь, если мы изменим биты, то это число станет 11010110. Теперь, чтобы достичь этого, вы должны сначала знать, как поменять местами два бита. Поменять местами два бита: - XOR оба бита с одним и посмотреть, если результаты отличаются. Если они не совпадают, то оба бита совпадают, иначе XOR оба бита с XOR и сохраните его в своем первоначальном номере; Теперь для изменения числа FOR I меньше чем Numberofbits / 2 swap (Number, I, NumberOfBits-1-I);

0
29.07.2013 04:02:19