|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 03 Mar 2003 18:49:30
To : Michael Sedov
Subject : Re: Операции над целыми числами.
--------------------------------------------------------------------------------
Michael Sedov wrote:
> Вопрос таков: какие более-менее полезные операции над целыми
> числами можно выразить через побитовые логические and, or, xor, not.
Hу много таких.... Вот дюжина примеров навскидку:
0. Актеры:
int x, y, mask;
"**" - операция возведения в степень
1. Взять остаток от деления числа на 2**n
(то же самое - n младших битов):
y = x & mаsk; где mask == 2**n - 1;
2. Проверить, принадлежит ли число множеству 2**n:
if((x & (x - 1)) { не принадлежит }
else { принадлежит }
3. Hайти наибольший делитель числа из множества 2**n
(то же самое - взять младший бит числа):
y = x & -x;
4. Оптимизация (для некоторых платформ)
выражения if(x < 0 || y < 0):
if((x|y) < 0)
Аналогичные логические выражения для
>=0, >0, ==0 оставляю в качестве домашнего задания
5. Проверить число на нечетность:
if(x & 1) { нечетное }
else { четное }
Модификацию "делится на 2**n"
оставляю в качестве домашнего задания.
6. Получить "выравнивание по четности в большую сторону"
- первое четное число, большее или равное x. То есть:
x y
1 2
2 2
3 4
4 4
5 6
6 6
и так далее:
y = (x + 1) & ~1;
Опять таки: выражения для "в меньшую сторону",
а также для выравнивания по другим степеням двойки
оставляю в качестве домашнего задания.
7. Оптимизация выражения "у чисел разный знак"
if(x < 0 && y >= 0 || x >= 0 && y < 0):
if((x ^ y) < 0) { знак разный }
else { знак одинаковый }
******* Так. Про числа пока хватит. Переходим к буквам. *******
8. Сделать транслитерацию к маленьким буквам
(ASCII table or KOI-8), т.e. tr/A-Z/a-z/:
y = x | ' ';
9. Сделать транслитерацию к заглавным буквам
(ASCII table or KOI-8), т.e. tr/a-z/A-Z/:
y = x & ~' ';
10. Сделать транслитерацию РУС<->ЛАТ в кодировке KOI-8:
y = x ^ 0240;
11. Сравнить две буквы (ASCII table or KOI-8)
без учета регистра (большие/маленькие):
if((x ^ y) & ~' ') { буквы разные }
else { буквы одинаковы }
12. Для заданого символа получить код его "CTRL-символа".
То есть для 'C' или 'c' это будет тройка:
y = x & 037;
Все, хватит. Прекращаю писать.
Обещаная дюжина примеров уже набралась.
Hадеюсь, этого достаточно для общего понимания
идей "практического применения битовых операций".
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
