неділя, 8 квітня 2012 р.

Битовые операции

   Добро пожаловать в мир двоичных чисел! 
   В "компьютерной арифметике" все данные сохраняются в двоичном виде. Операнды представляют собой битовые строки (или векторы) некоторой фиксированной длины. Выражения компьютерной арифметики похожи на выражения обычной арифметики, но в этом случае переменные обозначают содержимое регистров компьютера. Значение выражения компьютерной арифметики представляют собой строку битов без какой-либо специальной интерпретации; операнды же могут интерпретироваться по-разному. Например, в команде сравнения операнды интерпретируются либо как двоичные целые числа со знаком, либо как беззнаковые целые числа. Поэтому в зависимости от типов операндов, для обозначения оператора сравнения используются разные символы.

Часть I. Базовые битовые операции

   Наиболее распространённые операции битовой арифметики: побитовое "и", побитовое "или" и побитовое исключающее "или". Результат выполнения этих операций представлены в следующей таблице:

Операнды
побитовое
И
побитовое ИЛИ
побитовое исключающее ИЛИ
A
B
&
|
^
0
0
0
0
0
0
1
0
1
1
1
0
0
1
1
1
1
1
1
0
   Рассмотрим эти, а также некоторые другие операции и их использование более детально.
   §1.1 Сдвиг влево и сдвиг вправо (<< SHIFT LEFT, >> SHIFT RIGHT). Основная функция операций сдвиг влево (<< SHIFT LEFT) и сдвиг вправо (>> SHIFT RIGHT) - это сдвиг целочисельной переменной на указанное количество бит влево (или вправо), при этом старшие (или младшие) биты "исчезают", т.е. приобретают новые значения, старые значения при этом не сохраняются. Примеры:

Исходное
десятичное
число
Двоичное
представление
Операция
Новое
двоичное
представление
Новое
десятичное
значение
5 00000101 5 << 1 00001010 10
5 00000101 5 << 2 00010100 20
5 00000101 5 >> 1 00000010 2
5 00000101 5 >> 2 00000001 1
   Компьютерные поразрядные вычисления (битовые операции) выполняются быстрее арифметических, поэтому многие профессиональные программисты используют функции битового сдвига для замены операций деления нацело на 2 и умножения на 2. Преимущество такого использования проявляется в повышении эффективности выполнения программы, недостатком является более низкая читаемость подобного кода. Приведём пример подобного использования деления нацело на 2:
...
int n = 5;
n = n >> 1;
  // значение n = n/2
/ * Эту же формулу можно записать в виде n >> = 1 или n /= 2 */
...
   §1.2 Побитовое И (& AND). Это функция побитового сравнения двух целочисельных переменных, устанавливающая в новой переменной биты в состояние 1 только в том случае, если они оба равны 1 в исходных переменных.


Двоичное представление Десятичне значение
x
00000000000000000000000001110100
116
y
00000000000000000000000000101001
41
x & y
00000000000000000000000000100000
32
   Примером использования является подсчёт битов в заданном числе.

Первый способ Второй способ
...
int count_bit_1(int n)
{

 // считаем слева направо удаляя правый бит
    int c = 0;
    for (int i=0; i<32; ++i)  // int - 32-битная переменная
        if (n & (1 << i))
            c++;
    return c;
}
...
...
int count_bit_1(int n)
{
// то же,  но удаляя левый бит
    int c = 0;
    for (; n; n>>=1)
        if (n & 1)
            c++;
    return c;
}
...

   §1.3 Побитовое ИЛИ (| OR). Это функция побитового сравнения двух целочисельных переменных, устанавливающая в новой переменной биты в состояние 1 только в том случае, если хотя бы один из них равен 1 в исходных переменных.


Двоичное представление Десятичне значение
x
00000000000000000000000001110100
116
y
00000000000000000000000000101001
41
x | y
00000000000000000000000001111101
125
   Пример применения: установить 5-й бит в числе раным 1:
...
int mark_5th_bit(int n)
{
    return n | (1 << 4);
}
...
   §1.4 Побитовое исключительное ИЛИ (^ XOR). Это функция побитового сравнения двух целочисельных переменных, устанавливающая в новой переменной биты в состояние 1 только в том случае, если в одной и только в одной из исходных переменных один из рассматриваемых двух битов равен 1.


Двоичное представление Десятичне значение
x
00000000000000000000000001110100
116
y
00000000000000000000000000101001
41
x ^ y
00000000000000000000000001011101
93
   Пример применения: инвертировать 5-й бит в заданном числе:
...
int reverse_5th_bit(int n)
{
    return n ^ (1 << 4);
}
...
   §1.5 Побитовое инвертирование (~ NOT). Это функция побитового инвертирования целочисельной переменной, меняющая значение битов на обратные (0 на 1, а 1 на 0).


Двоичное представление Десятичне значение
x
00000000000000000000000000000011
3
~x
11111111111111111111111111111100
-4
   Следует отметить, что эту функцию можно применять и в других целях. Например, если в задаче нужно прочесть некоторое наперёд неизвестное количество целочисельных переменных, то это можно организовать так:

while(~scanf("%d",&n))
{
    …
}

Часть II. Битовые трюки

   §2.1 Манипуляции с младшими битами. Приведённые здесь формулы можно с успехом использовать для ускорения работы многих программ.
   Для того, чтобы обнулить крайний справа единичный бит (01011000=>01010000), использутся формула
x&(x-1)
   Эту формулу можно применять для проверки того, является ли беззнаковое целое степенью 2 (путём проверки результата вычислений на равенство 0).

   Обмен значений 2-х целочисельных переменных:

Первый способ Второй способ

void swap(int& x, int& y)
{
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
}
 

void swap(int& x, int& y)
{
    x ^= y ^= x ^= y;
}


   Проверка, является ли число степенью двойки:


bool ispow2(int n)
{
    return (n & -n) == n;
}
   Увеличить (уменьшить) целочисельную переменную на единицу:

Увеличить на 1 Уменьшить на 1

void add_one(int& x)
{
    return -~x; // ++x
}
… 

void sub_one(int& x)
{
    return ~-x; // --x
}
   Замена целого на противоположное:

Первый способ Второй способ

void negative(int& x)
{
    return ~x + 1;          // -x;
}
… 

void negative(int& x)
{
    return (x ^ -1) + 1;    // -x;
}
   Проверка целого на чётность (нечётность):


bool even_or_odd(int& x)
{
    return x & 1;   // x % 2;
}
   Вычисление остатка от деления на степень двойки:


int mod(int& x, int& m) // 
m должно быть степенью двойки
{
    return x & (m - 1); // 
x % m;
}
   Вычисление абсолютного значения целого числа:


int abs(int& x)
{
    
// x < 0 ? -x : x;
    return (x ^ (x >> 31)) - (x >> 31);
}
  Вычисление квадратного корня из обратного числа, т.е. для заданного целого n найти квадратный корень от 1/n:


// 1.0 / sqrt(x)
float InvSqrt(float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    x = *(float*)&i;
    x = x*(1.5f-xhalf*x*x);
    return x;
}
   Подсчёт количества значущих бит в 32-битном целом:

...
int count_bits(int& x)
{
        x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
        x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
        x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
        x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
        x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
        return x;
}
...
  В 32-битном целом поменять порядок битов на обратный:


int reverse_bits(int& x)
{
    x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
    x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
    x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
    x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
    x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
    return x;
}



 (Продолжение следует...)

1 коментар:

  1. The Eight-Wheel Classic - TITIAN Arts
    The eight-wheel 1xbet korean classic casino-roll.com bicycle is available in six sizes. The Bicycle Wheel is a mens titanium wedding bands classic bicycle made in 토토 사이트 도메인 USA, but there are three variations in

    ВідповістиВидалити