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

Question

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

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

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

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

Answer 1

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

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

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

Делать это вручную - это не так, как «С», как вы получите.

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

Answer 2

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

Answer 3

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

bFlipped = -1 - bInput;

Answer 4

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

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

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

Answer 5

Вот обязательное решение 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)]

Answer 6

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

Answer 7

Поскольку вопрос задан не-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);
}