Bitwise Operations Notes

БРОЙНИ СИСТЕМИ
=================================================

Формула за преобразуване от друга бройна система
в десетична: цифра * (основа^позиция)

Десетична бройна система
-------------------------------------------------
основа: 10
брой цифри: 10 (0 - 9)

3210 - позиции (индекси на цифрите)
2635 = 5 * 10^0 + 3 * 10^1 + 6 * 10^2 + 2 * 10^3
= 5*1 + 3*10 + 6*100 + 2*1000
= 5 + 30 + 600 + 2000 = 2635
-------------------------------------------------

Двоична бройна система
-------------------------------------------------
основа: 2
брой цифри: 2 (0 и 1)

43210 - позиции (индекси на цифрите)
10110 = 1 * 2^1 + 1 * 2^2 + 1 * 2^4 (разглеждаме
само позициите, на които има 1-ца)
= 2^1 + 2^2 + 2^4
= 2 + 4 + 16 = 22

Бърз начин за проверка на дали смятаме правилно:
нечетните числа имат 1 на позиция 0
-------------------------------------------------

Преобразуване от десетична в двоична система
-------------------------------------------------
Число: 35
Метод: Делим числото на основата (2), докато
не получим 0. Резултата от делението (целочислено)
продължаваме на делим, а остатъците запазваме.
Накрая взимаме остатъците в обратен ред

число / основа = резултат (остатък):
35 / 2 = 17 (1)
17 / 2 = 8 (1)
8 / 2 = 4 (0)
4 / 2 = 2 (0)
2 / 2 = 1 (0)
1 / 2 = 0 (1) // Приключваме при резултат 0

Остатъците в обратен ред са: 100011

Методът важи за всички бройни системи.
-------------------------------------------------

Представяне на числата в паметта
-------------------------------------------------
Числата се пазят в двоична система, като се
запълват отляво с водещи (незначещи нули). Броят
водещи нули зависи от типа - при 32-битови числа
общият брой битове е 32, т.е. числото 1 ще бъде:
0000 0000 0000 0000 0000 0000 0000 0001

Старши бит - битът на най-лявата позиция, това е
31-ва за тип int/uint.
При типовете със знак, които могат да приемат и
положителни, и отрицателни стойности, старшият бит
показва дали числото е положително - ако битът е
1, числото е отрицателно. При uint старшият бит е
просто 2^31.
=================================================

БИТОВИ ОПЕРАЦИИ
=================================================
Това са операции върху двоичното представяне на
числата (така, както се пазят в паметта).

Шест на брой: ~, ^, &, |, >>, <<

~ - negation
-------------------------------------------------
Описание: Сменя стойността на всички битове на
числото

Пример:
число: двоично представяне
5: 0000 0101
~5:1111 1010
Ако приемем, че работим с 8-битово число, стой-
ността на ~5 е 250 (ако работим с byte), или
-6 (ако работим с sbyte).
-------------------------------------------------

& - and
-------------------------------------------------
Описание: резултатът е число, което има 1-ци само
на тези позиции, на които и двата операнда имат
1-ци. На всички останали позиции резултатът има 0.

Пример:
10: 	1010
6: 		0110
10 & 6: 0010 (2 в десетична бройна система)

Само на позиция 1 и двете числа (10 и 6) имат 1 -
само там резултатът има 1-ца.
-------------------------------------------------

| - or
-------------------------------------------------
Описание: резултатът е число, което има 0-ли само
на тези позиции, на които и двата операнда имат
0-ли. На всички останали позиции резултатът има 1.

Пример:
10: 	1010
6: 		0110
10 | 6: 1110 (14)

Само на позиция 0 и двата операнда имат 0-ли,
както и на всички позиции след 3-та (водещите
нули, които игнорираме).
-------------------------------------------------

^ - xor (exclusive or)
-------------------------------------------------
Описание: Резултатът има 1-ца само когато двата
операнда имат различни стойности на тази позиция.
Т.е. имаме 1 в резултата ако имаме 1 и 0 в опера-
ндите; имаме 0 в резултата ако операндите имат
битове с еднаква стойност.

Пример:
10: 	1010
6: 		0110
10 ^ 6: 1100 (12)

На позиции 2 и 3 операндите имат различни стойно-
сти, докато на позиции 0 и 1 имат еднакви.
-------------------------------------------------

n >> p - right shift p times <=> n / 2^p
-------------------------------------------------
Описание: Изместваме битовете на числото p пъти
надясно. На най-лявата позиция добавяме 0.
Аналогично на целочислено деление на 2^p.

Пример:
10:			1010
10 >> 1 : 	0101 (5) <=> 10 / 2
10 >> 2:	0010 (2) <=> 10 / 2^2
-------------------------------------------------

n << p - left shift p times <=> n * 2^p
-------------------------------------------------
Описание: Изместваме битове на числото p пъти
наляво. На позиция 0 добавяме 0.
Аналогично на умножение по 2^p.

Пример:
6:			00110
6 << 1:		01100 (12) <=> 6 * 2
6 << 2:		11000 (24) <=> 6 * 2^2
=================================================

ПОЛЕЗНИ ФОРМУЛИ
=================================================

set bit at position p: number |= (1 << p)
-------------------------------------------------
Описание: на дадена позиция p искаме да сетнем
бита (да го направим 1), без значение каква е
стойността му.

Пример (искаме да сетнем бита на позиция 2):
10001 - number
00001 - 1
00100 - 1 << 2
10101 - number | (1 << 2)
-------------------------------------------------

unset bit at position p: number &= ~(1 << p)
-------------------------------------------------
Описание: на дадена позиция p искаме да занулим
бита (да го направим 0), без значение каква е
стойността му.

Пример (искаме да занулим бита на позиция 2):
10101 - number
00001 - 1
00100 - 1 << 2
11011 - ~(1 << 2) // водещите нули също са 1-ци
10001 - number & ~(1 << 2)
-------------------------------------------------

flip bit at position p: number ^= (1 << p)
-------------------------------------------------
Описание: Искаме да сменим стойността на бита на
дадена позиция - от 0 да го направим 1 или от
1 - 0.

Пример 1 (позиция 2):
10101 - number
00001 - 1
00100 - 1 << 2
10001 - number ^ (1 << 2)

Пример 2 (позиция 2):
10001 - number
00001 - 1
00100 - 1 << 2
10101 - number ^ (1 << 2)
-------------------------------------------------

check bit at position: (number >> p) & 1 == 1
-------------------------------------------------
Описание: Проверяваме на позиция p дали битът е
сетнат (1).

Пример (позиция 2):
10101 - number
00101 - number >> 2
00101 & 1 == 1 ? set : unset
-------------------------------------------------