Advertisement
Filkolev

Bitwise Operations Notes

Feb 27th, 2016
338
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.70 KB | None | 0 0
  1. БРОЙНИ СИСТЕМИ
  2. =================================================
  3.  
  4. Формула за преобразуване от друга бройна система
  5. в десетична: цифра * (основа^позиция)
  6.  
  7. Десетична бройна система
  8. -------------------------------------------------
  9. основа: 10
  10. брой цифри: 10 (0 - 9)
  11.  
  12. 3210 - позиции (индекси на цифрите)
  13. 2635 = 5 * 10^0 + 3 * 10^1 + 6 * 10^2 + 2 * 10^3
  14. = 5*1 + 3*10 + 6*100 + 2*1000
  15. = 5 + 30 + 600 + 2000 = 2635
  16. -------------------------------------------------
  17.  
  18. Двоична бройна система
  19. -------------------------------------------------
  20. основа: 2
  21. брой цифри: 2 (0 и 1)
  22.  
  23. 43210 - позиции (индекси на цифрите)
  24. 10110 = 1 * 2^1 + 1 * 2^2 + 1 * 2^4 (разглеждаме
  25. само позициите, на които има 1-ца)
  26. = 2^1 + 2^2 + 2^4
  27. = 2 + 4 + 16 = 22
  28.  
  29. Бърз начин за проверка на дали смятаме правилно:
  30. нечетните числа имат 1 на позиция 0
  31. -------------------------------------------------
  32.  
  33. Преобразуване от десетична в двоична система
  34. -------------------------------------------------
  35. Число: 35
  36. Метод: Делим числото на основата (2), докато
  37. не получим 0. Резултата от делението (целочислено)
  38. продължаваме на делим, а остатъците запазваме.
  39. Накрая взимаме остатъците в обратен ред
  40.  
  41. число / основа = резултат (остатък):
  42. 35 / 2 = 17 (1)
  43. 17 / 2 = 8 (1)
  44. 8 / 2 = 4 (0)
  45. 4 / 2 = 2 (0)
  46. 2 / 2 = 1 (0)
  47. 1 / 2 = 0 (1) // Приключваме при резултат 0
  48.  
  49. Остатъците в обратен ред са: 100011
  50.  
  51. Методът важи за всички бройни системи.
  52. -------------------------------------------------
  53.  
  54. Представяне на числата в паметта
  55. -------------------------------------------------
  56. Числата се пазят в двоична система, като се
  57. запълват отляво с водещи (незначещи нули). Броят
  58. водещи нули зависи от типа - при 32-битови числа
  59. общият брой битове е 32, т.е. числото 1 ще бъде:
  60. 0000 0000 0000 0000 0000 0000 0000 0001
  61.  
  62. Старши бит - битът на най-лявата позиция, това е
  63. 31-ва за тип int/uint.
  64. При типовете със знак, които могат да приемат и
  65. положителни, и отрицателни стойности, старшият бит
  66. показва дали числото е положително - ако битът е
  67. 1, числото е отрицателно. При uint старшият бит е
  68. просто 2^31.
  69. =================================================
  70.  
  71. БИТОВИ ОПЕРАЦИИ
  72. =================================================
  73. Това са операции върху двоичното представяне на
  74. числата (така, както се пазят в паметта).
  75.  
  76. Шест на брой: ~, ^, &, |, >>, <<
  77.  
  78. ~ - negation
  79. -------------------------------------------------
  80. Описание: Сменя стойността на всички битове на
  81. числото
  82.  
  83. Пример:
  84. число: двоично представяне
  85. 5: 0000 0101
  86. ~5:1111 1010
  87. Ако приемем, че работим с 8-битово число, стой-
  88. ността на ~5 е 250 (ако работим с byte), или
  89. -6 (ако работим с sbyte).
  90. -------------------------------------------------
  91.  
  92. & - and
  93. -------------------------------------------------
  94. Описание: резултатът е число, което има 1-ци само
  95. на тези позиции, на които и двата операнда имат
  96. 1-ци. На всички останали позиции резултатът има 0.
  97.  
  98. Пример:
  99. 10: 1010
  100. 6: 0110
  101. 10 & 6: 0010 (2 в десетична бройна система)
  102.  
  103. Само на позиция 1 и двете числа (10 и 6) имат 1 -
  104. само там резултатът има 1-ца.
  105. -------------------------------------------------
  106.  
  107. | - or
  108. -------------------------------------------------
  109. Описание: резултатът е число, което има 0-ли само
  110. на тези позиции, на които и двата операнда имат
  111. 0-ли. На всички останали позиции резултатът има 1.
  112.  
  113. Пример:
  114. 10: 1010
  115. 6: 0110
  116. 10 | 6: 1110 (14)
  117.  
  118. Само на позиция 0 и двата операнда имат 0-ли,
  119. както и на всички позиции след 3-та (водещите
  120. нули, които игнорираме).
  121. -------------------------------------------------
  122.  
  123. ^ - xor (exclusive or)
  124. -------------------------------------------------
  125. Описание: Резултатът има 1-ца само когато двата
  126. операнда имат различни стойности на тази позиция.
  127. Т.е. имаме 1 в резултата ако имаме 1 и 0 в опера-
  128. ндите; имаме 0 в резултата ако операндите имат
  129. битове с еднаква стойност.
  130.  
  131. Пример:
  132. 10: 1010
  133. 6: 0110
  134. 10 ^ 6: 1100 (12)
  135.  
  136. На позиции 2 и 3 операндите имат различни стойно-
  137. сти, докато на позиции 0 и 1 имат еднакви.
  138. -------------------------------------------------
  139.  
  140. n >> p - right shift p times <=> n / 2^p
  141. -------------------------------------------------
  142. Описание: Изместваме битовете на числото p пъти
  143. надясно. На най-лявата позиция добавяме 0.
  144. Аналогично на целочислено деление на 2^p.
  145.  
  146. Пример:
  147. 10: 1010
  148. 10 >> 1 : 0101 (5) <=> 10 / 2
  149. 10 >> 2: 0010 (2) <=> 10 / 2^2
  150. -------------------------------------------------
  151.  
  152. n << p - left shift p times <=> n * 2^p
  153. -------------------------------------------------
  154. Описание: Изместваме битове на числото p пъти
  155. наляво. На позиция 0 добавяме 0.
  156. Аналогично на умножение по 2^p.
  157.  
  158. Пример:
  159. 6: 00110
  160. 6 << 1: 01100 (12) <=> 6 * 2
  161. 6 << 2: 11000 (24) <=> 6 * 2^2
  162. =================================================
  163.  
  164. ПОЛЕЗНИ ФОРМУЛИ
  165. =================================================
  166.  
  167. set bit at position p: number |= (1 << p)
  168. -------------------------------------------------
  169. Описание: на дадена позиция p искаме да сетнем
  170. бита (да го направим 1), без значение каква е
  171. стойността му.
  172.  
  173. Пример (искаме да сетнем бита на позиция 2):
  174. 10001 - number
  175. 00001 - 1
  176. 00100 - 1 << 2
  177. 10101 - number | (1 << 2)
  178. -------------------------------------------------
  179.  
  180. unset bit at position p: number &= ~(1 << p)
  181. -------------------------------------------------
  182. Описание: на дадена позиция p искаме да занулим
  183. бита (да го направим 0), без значение каква е
  184. стойността му.
  185.  
  186. Пример (искаме да занулим бита на позиция 2):
  187. 10101 - number
  188. 00001 - 1
  189. 00100 - 1 << 2
  190. 11011 - ~(1 << 2) // водещите нули също са 1-ци
  191. 10001 - number & ~(1 << 2)
  192. -------------------------------------------------
  193.  
  194. flip bit at position p: number ^= (1 << p)
  195. -------------------------------------------------
  196. Описание: Искаме да сменим стойността на бита на
  197. дадена позиция - от 0 да го направим 1 или от
  198. 1 - 0.
  199.  
  200. Пример 1 (позиция 2):
  201. 10101 - number
  202. 00001 - 1
  203. 00100 - 1 << 2
  204. 10001 - number ^ (1 << 2)
  205.  
  206. Пример 2 (позиция 2):
  207. 10001 - number
  208. 00001 - 1
  209. 00100 - 1 << 2
  210. 10101 - number ^ (1 << 2)
  211. -------------------------------------------------
  212.  
  213. check bit at position: (number >> p) & 1 == 1
  214. -------------------------------------------------
  215. Описание: Проверяваме на позиция p дали битът е
  216. сетнат (1).
  217.  
  218. Пример (позиция 2):
  219. 10101 - number
  220. 00101 - number >> 2
  221. 00101 & 1 == 1 ? set : unset
  222. -------------------------------------------------
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement