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

Question

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

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

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

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

Answer 1

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

return 0;

Answer 2

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

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

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

Answer 3

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

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

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

Answer 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

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

Answer 5

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

Вот, пожалуйста:

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

Answer 6

Если вы говорите о переключении 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] }

♥ Рубин

Answer 7

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

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

Answer 8

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

Answer 9

А вот версия, напрямую вырезанная и вставленная из 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;
}

Answer 10

псевдокод ..

while (Read())
  Write(0);