276
правок
Изменения
→Применение для решения задач
*:Число, полученное в результате операции <tex>x\ \&\ (\sim x + 1)</tex> будет равно номеру младшего единичного бита в числе <tex>x</tex>.
*'''''Работа с битовыми масками'''''
*:Храним подмножества множества из <tex>32, 64</tex> или <tex>128</tex> фиксированных элементов. Значение каждого бита позволяет понять, включен элемент в множество или нет. Тогда легко сделать следующее: найти дополнение <tex>(\simmask)</tex>, пересечение <tex>(mask_1\ \&\ mask_2)</tex>, объединение <tex>(mask_1 \midmask_2)</tex> множеств, установить бит по номеру <tex>(mask \mid (1 \ll x))</tex>, снять бит по номеру <tex>(mask\ \& \ \sim(1 \ll x))</tex>.
*'''''Определение знака числа'''''
<code>
sign = (v != 0) | -('''int''')(('''unsigned int''')(('''int''')v) >> (''sizeof''('''int''') * CHAR_BIT - 1)); // Or, for more speed but less portability: sign = (v != 0) | (v >> (''sizeof''('''int''') * CHAR_BIT - 1)); // -1, 0, or +1 // Or, for portability, brevity, and (perhaps) speed: sign = (v > 0) - (v < 0); // -1, 0, or +1
</code>
*'''''[[Алгоритм Флойда]]'''''
*:Оптимизация с помощью битовых масок. Время работы <tex>O\Big(\dfrac{n^3}{k}\Big)</tex>.
*'''''[[Дерево Фенвика]]'''''
