Побитовые операции - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:40:16Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:38, 1 сентября 2022

2022-09-01T03:38:16Z

195.209.230.212: /* Побитовые сдвиги, поправлены символы операторов */

2020-03-10T09:09:08Z

‎Побитовые сдвиги, поправлены символы операторов

178.44.107.155: /* Нахождение минимума и максимума из двух чисел без использования условного оператора */

2019-01-03T13:13:20Z

‎Нахождение минимума и максимума из двух чисел без использования условного оператора

178.44.107.155: /* Вычисление модуля числа без использования условного оператора */

2019-01-03T12:55:09Z

‎Вычисление модуля числа без использования условного оператора

178.44.107.155: /* Нахождение минимума и максимума из двух чисел без использования условного оператора */

2019-01-03T12:51:27Z

‎Нахождение минимума и максимума из двух чисел без использования условного оператора

188.170.73.153: /* Алгоритм Флойда */

2017-12-30T15:50:28Z

‎Алгоритм Флойда

Pavponn в 20:02, 28 декабря 2017

2017-12-28T20:02:45Z

Pavponn: /* Алгоритм Флойда */

2017-12-28T14:51:03Z

‎Алгоритм Флойда

Pavponn: /* Алгоритм Флойда */

2017-12-28T14:49:33Z

‎Алгоритм Флойда

← Предыдущая		Версия 16:40, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Побитовые операции''' (англ. ''bitwise operations'') — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: [[Определение булевой функции \| логические операции]] и побитовые сдвиги.		'''Побитовые операции''' (англ. ''bitwise operations'') — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: [[Определение булевой функции \| логические операции]] и побитовые сдвиги.
	==Принцип работы==		==Принцип работы==

← Предыдущая		Версия 03:38, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Побитовые операции''' (англ. ''bitwise operations'') — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: [[Определение булевой функции \| логические операции]] и побитовые сдвиги.		'''Побитовые операции''' (англ. ''bitwise operations'') — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: [[Определение булевой функции \| логические операции]] и побитовые сдвиги.
	==Принцип работы==		==Принцип работы==

@@ Строка 44: / Строка 44: @@
 ===Побитовые сдвиги===
-Операторы сдвига <tex>\texttt{<<}</tex> и <tex>\texttt{>>}</tex> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Дополнительный код (дополнение до двух) | двоичном дополнительном коде]] и необходимо поддерживать знаковый бит).
+Операторы сдвига <tex><<</tex> и <tex>{>>}</tex> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Дополнительный код (дополнение до двух) | двоичном дополнительном коде]] и необходимо поддерживать знаковый бит).
 Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
@@ Строка 55: / Строка 55: @@
 </code>
-В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>\texttt{>>>}</tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
+В языке программирования Java существует также оператор беззнакового битового сдвига вправо <tex>>>></tex>. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
 <code>

@@ Строка 95: / Строка 95: @@
 Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
-Пусть даны числа <tex>x</tex> и <tex>y</tex> разрядности <tex>n</tex>. Тогда, если <tex>x < y</tex>, то <tex>((x - y) >> (n - 1)) = -1</tex> а если <tex>x \geqslant y</tex>, то <tex>((x - y) >> (n - 1)) = 0</tex>. Выражение <tex>((x - y) \& ((x - y) >> (n - 1))</tex> принимает значение <tex>0</tex>, если <tex>x \geqslant y</tex> и <tex>(x - y)</tex>, если <tex>x < y</tex>.
+Пусть даны числа <tex>x</tex> и <tex>y</tex> разрядности <tex>n</tex>. Тогда если <tex>x < y</tex>, то <tex>((x - y) >> (n - 1)) = -1</tex>, а если <tex>x \geqslant y</tex>, то <tex>((x - y) >> (n - 1)) = 0</tex>. Выражение <tex>((x - y) \& ((x - y) >> (n - 1))</tex> принимает значение <tex>0</tex>, если <tex>x \geqslant y</tex>, и <tex>(x - y)</tex>, если <tex>x < y</tex>.
 <code>
   '''int32''' min(x, y: '''int32'''):

@@ Строка 85: / Строка 85: @@
   '''int32''' abs1(x: '''int32'''):
       mask = x >> 31
-      '''return''' (x + mask) <tex>\oplus</tex> mask
+      '''return''' (x + mask) '''XOR''' mask
   '''int32''' abs2(x: '''int32'''):
       mask = x >> 31
-      '''return''' (x <tex>\oplus</tex> mask) - mask
+      '''return''' (x + mask) '''XOR''' mask
 </code>

@@ Строка 199: / Строка 199: @@
 ====Алгоритм Флойда====
 {{main|Алгоритм Флойда}}
-'''Алгоритм Флойда–Уоршелла''' (англ. ''the Floyd–Warshall algorithm'') {{---}}  алгоритм, разработанный в  <tex>1962</tex> году Робертом Флойдом <ref> [https://ru.wikipedia.org/wiki/Флойд_Роберт Роберт Флойд]</ref> и Стивеном Уоршеллом <ref> [https://en.wikipedia.org/wiki/Stephen_Warshall Cтивен Уоршелл]</ref> для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex> \Theta(n^3) </tex>, также требует <tex> \Theta(n^2) </tex> памяти.
+'''Алгоритм Флойда–Уоршелла''' (англ. ''the Floyd–Warshall algorithm'') {{---}}  алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex> \Theta(n^3) </tex>, также требует <tex> \Theta(n^2) </tex> памяти.
 ====Дерево Фенвика====

@@ Строка 125: / Строка 125: @@
   '''int32''' greatestBit(x: '''int32'''):
       power = 1
-      '''for''' i = 1..<tex>\log_2{32}</tex>:
+      '''for''' i = 1 <tex> \ldots\log_2{32}</tex>:
           x |= x >> power
           power <<= 1
@@ Строка 212: / Строка 212: @@
 Функция, позволяющая делать операции вставки и изменения элемента за <tex> O(\log n) </tex>, задается следующей формулой <tex> F(i) = (i \And (i + 1)) </tex>.
-Пусть дан массив <tex> A = [a_0, a_1, \ldots, a_{n - 1}]</tex>.  Деревом Фенвика  называется  массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k</tex>, где <tex> i = 0 .. n - 1 </tex> и <tex> F(i) </tex> — функция, которую мы определили ранее.
+Пусть дан массив <tex> A = [a_0, a_1, \ldots, a_{n - 1}]</tex>.  Деревом Фенвика  называется  массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k</tex>, где <tex> i = 0\ldots n - 1 </tex> и <tex> F(i) </tex> — функция, которую мы определили ранее.
 ==См. также==