Изучите следующие две функции:
bool GetBit(int value, int bit_position)
{
return value & (1 << bit_position);
}
void SetBit(int& value, int bit_position, bool new_bit_value)
{
if (new_bit_value)
value |= (1 << bit_position);
else
value &= ~(1 << bit_position);
}
Итак, теперь мы можем читать и записывать произвольные биты, как массив.
1 << N
дает вам:
000...0001000...000
Где 1 находится в N-й позиции.
Итак
1 << 0 == 0000...0000001
1 << 1 == 0000...0000010
1 << 2 == 0000...0000100
1 << 3 == 0000...0001000
...
и т. Д.
Что теперь произойдет, если я BINARY И один из приведенных выше чиселс каким-то другим числом Y?
X = 1 << N
Z = X & Y
Как будет выглядеть Z?Ну, каждый бит кроме Nth определенно будет 0, не так ли?потому что эти биты равны 0 в X.
Каким будет N-й бит Z?Это зависит от значения N-го бита Y, не так ли?Итак, при каких обстоятельствах Z ноль?Именно тогда, когда N-й бит Y равен 0. Поэтому, преобразовав Z в логическое значение, мы можем отделить значение N-го бита Y. Еще раз взглянем на приведенную выше функцию GetBit, это именно то, что она делает.
Теперь, когда мы читаем биты, как мы можем установить бит?Ну, если мы хотим установить бит, мы можем использовать BINARY OR с одним из (1 << N) чисел сверху: </p>
X = 1 << N
Z = Y | X
Что Z будет здесь?Ну, каждый бит будет таким же, как Y, кроме N-го, верно?И N-й бит всегда будет равен 1. Итак, мы установили N-й бит.
Как насчет установки бита в ноль?То, что мы хотим сделать, это взять число типа 11111011111, где только N-й бит выключен, и затем использовать BINARY AND.Чтобы получить такое число, мы просто используем BINARY NOT:
X = 1 << N // 000010000
W = ~X // 111101111
Z = W & Y
Таким образом, все биты в Z, кроме N-го, будут копиями Y. N-й всегда будет выключен.Таким образом, мы фактически установили N-й бит равным 0.
Используя вышеописанные два метода, мы реализовали SetBit.
Так что теперь мы можем читать и записывать произвольные биты.Теперь мы можем обратить биты числа так же, как это было в массиве:
int ReverseBits(int input)
{
int output = 0;
for (int i = 0; i < N; i++)
{
bool bit = GetBit(input, i); // read ith bit
SetBit(output, N-i-1, bit); // write (N-i-1)th bit
}
return output;
}
Пожалуйста, убедитесь, что вы все это понимаете.Как только вы все это поняли, закройте страницу, внедрите и протестируйте их, не глядя на нее.
Если вам понравилось, попробуйте некоторые из них:
http://graphics.stanford.edu/~seander/bithacks.html
И / или получите эту книгу:
http://www.amazon.com/exec/obidos/ASIN/0201914654/qid%3D1033395248/sr%3D11-1/ref%3Dsr_11_1/104-7035682-9311161