Как изменить значение бита на противоположное

Начал изучать Java

   
15.06.2021
09:41   

нет комментариев

Выбрал базовый курс по Java на Stepic.org

Пока что все выглядит, как в анекдоте «Два плюс два равно четыре, а теперь решите тригонометрическое уравнение».

Похоже, что курс рассчитан на самостоятельное гугление. Тем не менее комментарии к задачам позволяют найти правильный путь.

Зачем мне Java, не случиться ли с ней тоже самой что с Machine Learning или Django? Надеюсь, что нет. Есть несколько компонентов облачной технологии 1С:Фреш, которые написаны на Java. Также есть 1C:EDT, который написан также на Java. Так что надеюсь, что эти знания не пропадут и будут использоваться на практике.

Понравилась задачка в самом начале:

Реализуйте метод flipBit, изменяющий значение одного бита заданного целого числа на противоположное. Данная задача актуальна, например, при работе с битовыми полями.
Договоримся, что биты нумеруются от младшего (индекс 1) к старшему (индекс 32).

Тут нужно понять что вообще требуется.

Для начала нужно понять, что параметр bitIndex — это индекс места единички в двоичном представлении числа. Т.е. если bitIndex = 1, то смещение должно выглядеть как 0001, если bitIndex = 2, то смещение должно выглядеть как 0010 и так далее. Тут я указал 4 цифры двоичного числа для краткости. Например если bitIndex = 7, то в двоичном виде это будет 1000000. Будем использовать единицу для смещения битов. При этом, если bitIndex = 1, то никакого смещения не требуется, т.к. мы уже находимся там где нужно. Чтобы получить нужное смещение, нужно вычесть из значения bitIndex единицу и для единицы сделать смещение битов влево, используя оператор cмещения — << .

Дальше нужно поменять значение бита у числа. Для этого нужно вспомнить как ведет себя операция XOR.

a  b xor
0  0  0  // ничего не происходит с битом
0  1  1  // бит a меняется на противоположный 0 -> 1
1  0  1  // ничего не происходит с битом
1  1  0  // бит a меняется на противоположный 1 -> 0

В результате получим решение:

public static int flipBit(int value, int bitIndex) {
    return value ^ (1 << --bitIndex);
}

Интереснее будет решение, если расширить выводимую информацию:

public static int flipBit(int value, int bitIndex) {
    int result = value ^ (1 << bitIndex - 1);
    System.out.println(value + " (" + Integer.toBinaryString(value) + ") и " + bitIndex
            + " (" + Integer.toBinaryString(1 << bitIndex - 1)
            + ") = " + result
            + " (" + Integer.toBinaryString(result) + ")");
    return result;
}

Тут становится понятно, что происходит, если поэкспериментировать с параметрами. Изменяется значение одного бита заданного целого числа на противоположное (убрал вывод и добавил пробелов, чтобы было понятнее):

65 (1000001) и 1        (1) = 64   (1000000)
65 (1000001) и 2       (10) = 67   (1000011)
65 (1000001) и 3      (100) = 69   (1000101)
65 (1000001) и 8 (10000000) = 193 (11000001)
65 (1000001) и 7  (1000000) = 1          (1)

На простом примере из первой строки есть число 65 — это 1000001 в двоичном виде. Хотим поменять первый бит на противоположный, получим 1000000 в двоичном виде — это число 64 в десятиричном. И так далее.

Введение

Язык Си иногда называют макроассемблером за его тягу к железу. Если не использовать оптимизацию, можно даже примерно оценить, в какие конструкции на ассемблере
преобразуется код программы. Простота и минимализм языка (простоту языка не путать с простотой программирования на языке)
привели к тому, что на многих платформах си остаётся единственным высокоуровневым языком программирования. Без обзора побитовых операций, конечно, изучения языка было
бы неполным.

Побитовые операции, как понятно из названия, позволяют оперировать непосредственно с битами. Большое количество примеров использования побитовых операций можно найти, например,
в книге Генри Уоррена «Алгоритмические трюки для программистов». Здесь мы рассмотрим только сами операции и примитивные алгоритмы.

Побитовые И, ИЛИ, НЕ, исключающее ИЛИ

ЗАМЕЧАНИЕ: здесь и далее в примерах используются 8-битные числа для упрощения записи. Всё это верно и для любых других чисел.

Напомню для начала, что логические операции И, ИЛИ, исключающее ИЛИ и НЕ могут быть описаны с помощью таблиц истинности

В побитовых (bit-wise) операциях значение бита, равное 1, рассматривается как логическая истина, а 0 как ложь. Побитовое И (оператор &) берёт два числа и логически умножает
соответствующие биты. Например, если логически умножить 3 на 8, то получим 0

char a = 3;
char b = 8;
char c = a & b;
printf("%d", c);

Так как в двоичном виде 3 в виде однобайтного целого представляет собой


00000011


а 8


00001000


Первый бит переменной c равен логическому произведению первого бита числа a и первого бита числа b. И так для каждого бита.

00000011
00001000
↓↓↓↓↓↓↓↓
00000000


Соответственно, побитовое произведение чисел 31 и 17 даст 17, так как 31 это

00011111

, а 17 это

00010001


00011111
00010001
↓↓↓↓↓↓↓↓
00010001


Побитовое произведение чисел 35 и 15 равно 3.

00100011
00001111
↓↓↓↓↓↓↓↓
00000011


Аналогично работает операция побитового ИЛИ (оператор |), за исключением того, что она логически суммирует соответствующие биты чисел без переноса.

Например,

char a = 15;
char b = 11;
char c = a | b;
printf("%d", c);

выведет 15, так как 15 это 00001111, а 11 это 00001011

00001111
00001011
↓↓↓↓↓↓↓↓
00001111


Побитовое ИЛИ для чисел 33 и 11 вернёт 43, так как 33 это 00100001, а 11 это 00001011

00100001
00001011
↓↓↓↓↓↓↓↓
00101011


Побитовое отрицание (оператор ~) работает не для отдельного бита, а для всего числа целиком. Оператор инверсии меняет ложь на истину, а истину на ложь, для каждого бита.
Например,

char a = 65;
char b = ~a;
printf("%d", b);

Выведет -66, так как 65 это 01000001, а инверсия даст 10111110

что равно -66. Кстати, вот алгоритм для того, чтобы сделать число отрицательным: для нахождение дополнительного кода числа его надо инвертировать и
прибавить к нему единицу.

char a = 107;
char b = ~a + 1;
printf("a = %d, -a = %d", a, b);

Исключающее ИЛИ (оператор ^) применяет побитово операцию XOR. Например, для чисел

char a = 12;
char b = 85;
char c = a ^ b;
printf("%d", c);

будет выведено 89, так как a равно 00001100, а b равно 01010101. В итоге получим 01011001

Иногда логические операторы && и || путают с операторами & и |. Такие ошибки могут существовать в коде достаточно долго,
потому что такой код в ряде случаев будет работать. Например, для чисел 1 и 0. Но так как в си истиной является любое ненулевое значение,
то побитовое умножение чисел 3 и 4 вернёт 0, хотя логическое умножение должно вернуть истину.

int a = 3;
int b = 4;
printf("a & b = %dn", a & b);	//выведет 0
printf("a && b = %dn", a && b);//выведет не 0 (конкретнее, 1)

Операции побитового сдвига

Операций сдвига две – битовый сдвиг влево (оператор <<) и битовый сдвиг вправо (оператор >>). Битовый сдвиг вправо сдвигает биты числа
вправо, дописывая слева нули. Битовый сдвиг влево делает противоположное: сдвигает биты влево, дописывая справа нули. Вышедшие за пределы числа биты отбрасываются.

Например, сдвиг числа 5 влево на 2 позиции


00000101 << 2 == 00010100


Сдвиг числа 19 вправо на 3 позиции

00010011 >> 3 == 00000010

Независимо от архитектуры (big-endian, или little-endian, или middle-endian) числа в двоичном виде представляются слева направо, от более значащего бита к менее значащему.
Побитовый сдвиг принимает два операнда – число, над которым необходимо произвести сдвиг, и число бит, на которое необходимо произвести сдвиг.

int a = 12;
printf("%d << 1 == %dn", a, a << 1);
printf("%d << 2 == %dn", a, a << 2);
printf("%d >> 1 == %dn", a, a >> 1);
printf("%d >> 2 == %dn", a, a >> 2);

Так как сдвиг вправо (>>) дописывает слева нули, то для целых чисел операция равносильна целочисленному делению пополам, а сдвиг влево умножению на 2.
Произвести битовый сдвиг для числа с плавающей точкой без явного приведения типа нельзя. Это вызвано тем, что
для си не определено представление числа с плавающей точкой. Однако можно переместить число типа float в int, затем сдвинуть и вернуть обратно

float b = 10.0f;
float c = (float) (*((unsigned int*)&b) >> 2);
printf("%.3f >> 2 = %.3f", b, c);

Но мы, конечно же, получим не 5.0f, а совершенно другое число.

Особенностью операторов сдвига является то, что они могут по-разному вести себя с числами со знаком и без знака, в зависимости
от компилятора. Действительно, отрицательное число обычно содержит один бит знака. Когда мы будем производить сдвиг влево, он может пропасть, число станет
положительным. Однако, компилятор может сделать так, что сдвиг останется знакопостоянным и будет проходить по другим правилам. То
же самое и для сдвига вправо.

unsigned int ua = 12;
signed int sa   = -11;
printf("ua = %d, ua >> 2 = %dn", ua, ua >> 2);
printf("sa = %d, sa >> 2 = %dn", sa, sa >> 2);
printf("(unsigned) sa = %u, sa >> 2 = %un", sa, sa >> 2);
printf("sa = %d, ((unsigned) sa) >> 2 = %d", sa, ((unsigned) sa) >> 2);

В данном случае при первом сдвиге всё работает, как и задумано, потому что число без знака. Во втором случае компилятор VSE2013 оставляет знак. Однако если посмотреть на
представление этого числа, как беззнакового, сдвиг происходит по другим правилам, с сохранением самого левого бита. В последней строчке, если привести число со знаком к
числу без знака, то произойдёт обычный сдвиг, и мы получим в результате положительное число.

Побитовые операторы и операторы сдвига не изменяют значения числа, возвращая новое. Они также как и арифметические операторы, могут входить в состав сложного присваивания

int a = 10;
int b = 1;
a >>= 3;
a ^= (b << 3);

и т.д.

Примеры

1. Напишем функции, которые позволяют определять и изменять определённый бит числа

Для того, чтобы узнать, какой бит (1 или 0) стоит на позиции n, воспользуемся логическим умножением.

Пусть имеется число 9

00001001

Нужно узнать, выставлен ли бит на позиции 3 (начиная с нуля). Для этого умножим его на число, у которого все биты равны нулю, кроме третьего:


00001001 & 00001000 = 00001000


Теперь узнаем значение бита в позиции 6


00001001 & 01000000 = 00000000


Таким образом, если мы получаем ответ, равный нулю, то на искомой позиции находится ноль, иначе единица. Чтобы получить число, состоящее из нулей с одним битом на нужной позиции, сдвинем 1 на нужное число бит влево.

#include <stdio.h>
#include <conio.h>
#include <limits.h>

int checkbit(const int value, const int position) {
	int result;
	if ((value & (1 << position)) == 0) {
		result = 0;
	} else {
		result = 1;
	}
	return result;
}

void main() {
	int a = 3;
	size_t len = sizeof(int) * CHAR_BIT;
	size_t i;

	for (i = 0; i < len; i++) {
		printf("%d", checkbit(a, i));
	}

	_getch();
}

Заметьте, что в функции условие записано так

(value & (1 << position)) == 0

Потому что без скобок сначала будет вычислено равенство нулю и только потом выполнено умножение.

value & (1 << position) == 0

Функцию можно упростить

int checkbit(const int value, const int position) {
	return ((value & (1 << position)) != 0);
}

Функция, которая выставляет бит на n-й позиции в единицу.

Известно, что логическое сложение любого бита с 1 будет равно 1. Так что для установки n-го бита нужно логически сложить число с таким, у которого все биты, кроме нужного,
равны нулю. Как получить такое число, уже рассмотрено.

int setbit(const int value, const int position) {
	return (value | (1 << position));
}

Функция, которая устанавливает бит на n-й позиции в ноль.

Для этого нужно, чтобы все биты числа, кроме n-го, не изменились. Умножим число на такое, у которого все биты равны единице, кроме бита под номером n. Например


0001011 & 1110111 = 0000011


Чтобы получить такую маску, сначала создадим число с нулями и одной единицей, а потом инвертируем его.

int unsetbit(const int value, const int position) {
	return (value & ~(1 << position));
}

Функция, изменющая значение n-го бита на противоположное.

Для этого воспользуемся функцией исключающего или: применим операцию XOR к числу, которое состоит из одних нулей и одной единицы на месте нужного бита.

int switchbit(const int value, const int position) {
	return (value ^ (1 << position));
}

Проверка

#include <stdio.h>
#include <conio.h>
#include <limits.h>

int checkbit(const int value, const int position) {
	return ((value & (1 << position)) != 0);
}

int setbit(const int value, const int position) {
	return (value | (1 << position));
}

int unsetbit(const int value, const int position) {
	return (value & ~(1 << position));
}

int switchbit(const int value, const int position) {
	return (value ^ (1 << position));
}

void printbits(int n) {
	//CHAR_BIT опеределён в библиотеке limits.h
	//и хранит число бит в байте для данной платформы
	size_t len = sizeof(int)* CHAR_BIT;
	size_t i;
	for (i = 0; i < len; i++) {
		printf("%d", checkbit(n, i));
	}
	printf("n");
}

void main() {
	int a = 3;
	size_t len = sizeof(int) * CHAR_BIT;
	size_t i;

	printbits(a);
	a = setbit(a, 5);
	printbits(a);
	a = unsetbit(a, 5);
	printbits(a);
	a = switchbit(a, 11);
	printbits(a);
	a = switchbit(a, 11);
	printbits(a);

	_getch();
}

Битовые флаги

Расммотрим синтетический пример. Пусть у нас есть три логические переменные, и нам нужно вывести определённое значение
в зависимости от всех этих переменных сразу. Очевидно, что может быть 2³ возможных вариантов. Запишем
это условие в виде ветвления:

#include <stdio.h>

int main() {
	unsigned char a, b, c;
	a = 1;
	b = 0;
	c = 0;

	if (a) {
		if (b) {
			if (c) {
				printf("true true true");
			} else {
				printf("true true false");
			}
		} else {
			if (c) {
				printf("true false true");
			} else {
				printf("true false false");
			}
		}
	} else {
		if (b) {
			if (c) {
				printf("false true true");
			}
			else {
				printf("false true false");
			}
		}
		else {
			if (c) {
				printf("false false true");
			}
			else {
				printf("false false false");
			}
		}
	}

	_getch();
	return 0;
}

Мы получили 8 ветвей. Пусть теперь нам понадобилось добавить ещё одно условие. Тогда число ветвей удвоится, и программа
станет ещё сложней для понимания и отладки. Перепишем пример.

Если каждое из наших логичесих значений сдвинуть на своё число бит влево и логически сложить, то мы получим свою уникальную
комбинацию бит в зависимоти от значений a, b и c:

#include <stdio.h>
#include <limits.h>

void printbits (int n) {
	int i;
	for (i = CHAR_BIT - 1; i >= 0; i--) {
		printf("%d", (n & (1 << i)) != 0);
	}
	printf("n");
}

int main() {
	unsigned char a, b, c;
	unsigned char res;

	a = 1; b = 0; c = 0;
	res = c | b << 1 | a << 2;
	printbits(res);

	a = 0; b = 1; c = 1;
	res = c | b << 1 | a << 2;
	printbits(res);

	a = 1; b = 0; c = 1;
	res = c | b << 1 | a << 2;
	printbits(res);

	_getch();
	return 0;
}

Используем этот подход к нашей задаче и заменим ветвеление на switch:

#include <stdio.h>

int main() {
	unsigned char a, b, c;
	unsigned char res;
	a = 1;
	b = 0;
	c = 0;

	res = c | b<< 1 | a << 2;
	switch (res) {
	case 0b00000000:
		printf("false false false");
		break;
	case 0b00000001:
		printf("false false true");
		break;
	case 0b00000010:
		printf("false true false");
		break;
	case 0b00000011:
		printf("false true true");
		break;
	case 0b00000100:
		printf("true false false");
		break;
	case 0b00000101:
		printf("true false true");
		break;
	case 0b00000110:
		printf("true true false");
		break;
	case 0b00000111:
		printf("true true true");
		break;
	}

	_getch();
	return 0;
}

Этот метод очень часто используется для назначения опций функций в разных языках программирования. Каждый
флаг принимает своё уникальное название, а их совместное значение как логическая сумма всех используемых флагов.
Например, библиотека fcntl:

char *fp = "/home/ec2-user/file.txt";
int flag = O_RDWR | O_CREAT | O_TRUNC | O_APPEND;
int fd = open(fp, flag, 0644);

Здесь флаг O_RDWR рaвен


00000000000000000000000000000010


O_CREAT рaвен


00000000000000000000000100000000


O_TRUNC равен


00000000000000000000001000000000

и O_APPEND


00000000000000000000000000001000


Q&A

Об аргументах функции

Для тех кому надо освежить знания оставлю тут памятку, более подробно эти операции будут рассмотрены в статье.

установить нулевой бит
PORTB | = 0x01;

сбростить нулевой бит
PORTB &= ~0x01;

проверить установлен ли бит
if(PORTB & 0x01)
{

}

инвертировать значение нулевого бита
#define    LED    0x01 
PORTB ^= LED;

Независимо от того какие микроконтроллеры Вы собираетесь программировать, первое что придётся освоить — это битовые операции.
Битовых операций в языке Си всего 6.

& ( AND )
| ( OR )
^ ( XOR )
~  ( NOT )
<<(сдвиг влево)
>>(сдвиг вправо)

Начнем с того, что выводы микроконтроллера условно разделены на порты, у Atmega16 порт состоит из 8 выводов, у STM32f103 из 16 выводов.

Отмеченные ножки, как раз и составляют порт А.
Побитовое ИЛИ — результат операции равен 1, если один из соответствующих битов равен 1, иначе 0.

Установить в 1 нулевой бит порта B можно следующим образом.

PORTB = 0x01; //шестнадцатеричная запись
или
PORTB = 0b00000001; //двоичная запись
или
PORTB = 1; //десятичная запись

Таким образом, мы установили нулевой бит в 1, а все остальные в 0, то есть мы переопределили все биты порта. А что если мы хотим установить в 1 только нулевой бит и не задеть остальные? В таком случае нужно воспользоваться побитовым ИЛИ.

установить нулевой бит в единицу
PORTB = PORTB | 0x01;
или воспользовавшись составным присваиванием
PORTB | = 0x01;

В результате мы изменили только нулевой бит порта.
Надо отметить, что в микроконтроллерах счёт начинается с нуля, то есть первый бит будет иметь нулевой порядковый номер, а порядковый номер восьмого бита будет 7.

Битовая операция НЕ — изменяет значение бита на противоположное.

Побитовое И — если соответствующие биты равны 1, результирующий бит равен 1. Если один из соответствующих битов равен 0, то результирующий бит равен 0.

Эта операция совместно с битовым НЕ может использоваться для сброса конкретного бита в ноль.

сростить нулевой бит
PORTB &= 0xFE;
или
PORTB &= ~0x01;

При такой записи, мы выставляем в единицу бит, который хотим обнулить, затем инвертируем получившееся число

Теперь накладываем получившуюся маску

В итоге мы выставили в 0 только первый бит.

Также эту операцию можно использовать для проверки чему равен бит. Например, нам надо проверить чему равен нулевой бит порта B, это можно сделать с помощью следующей конструкции.

if(PORTB & 0x01)

Если бит равен единице, выражение в скобках будет правда, иначе — ложь.

Побитовое исключающее ИЛИ — если сумма соответствующих битов число чётное, результирующий бит 0, иначе 1.

С помощью этой операции можно инвертировать состояние выбранного бита. Например, к нулевому выводу порта подключен светодиод и при выполнении одного и того же фрагмента кода, мы хотим чтобы он погас если горит и наоборот, зажёгся если не горит.

#define    LED    0x01 
PORTB ^= LED;

Также с помощью этой операции можно определить равенство регистров. Например, мы хотим сравнить в одинаковом ли состоянии находятся порты B и D.

if(PORTB ^ PORTD)

Если результат равен нулю, то содержимое регистров равно.

Логический сдвиг влево — все разряды при этом сдвигаются на одну позицию влево, самый левый бит теряется, а в самый правый бит записывается 0.

Операция логического сдвига влево эквивалентна умножению на 2.
0b0000 1011 = 11
0b0001 0110 = 22

Логический сдвиг вправо — все разряды при этом сдвигаются на одну позицию вправо, самый правый бит теряется, а в самый левый бит записывается 0.

Операция логического сдвига влево эквивалентна делению на 2.
0b1000 1011 = 147
0b0100 0101 = 73
Видно, что при делении на 2 результат округляется в меньшую сторону, на этом всё.

В этой статье я расскажу вам о том, как работают битовые операции. С первого взгляда они могут показаться вам чем-то сложным и бесполезным, но на самом деле это совсем не так. В этом я и попытаюсь вас убедить.

Введение

Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.

Я расскажу о следующих побитовых операторах:

• |  (Побитовое ИЛИ (OR)),
• & (Побитовое И (AND)),
• ^ (Исключающее ИЛИ (XOR)),
• ~ (Побитовое отрицание (NOT)),
• << (Побитовый сдвиг влево),
• >> (Побитовый сдвиг вправо).

Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.

О битовых операторах вам также необходимо знать:

1. Некоторые побитовые операторы похожи на операторы, с которыми вы наверняка знакомы (&&, ||). Это потому, что они на самом деле в чем-то похожи. Тем не менее, путать их ни в коем случае нельзя.
2. Большинство битовых операций являются операциями составного присваивания.

Побитовое ИЛИ (OR)

Побитовое ИЛИ действует эквивалентно логическому ИЛИ, но примененному к каждой паре битов двоичного числа. Двоичный разряд результата равен 0 только тогда, когда оба соответствующих бита в равны 0. Во всех других случаях двоичный результат равен 1. То есть, если у нас есть следующая таблица истинности:

38 | 53 будет таким:

В итоге мы получаем 110111₂ , или 55₁₀ .

Побитовое И (AND)

Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:

Пример работы побитового И на выражении 38 & 53:

Как результат, получаем 100100₂ , или 36₁₀ .

С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 1, то число нечетное (основываясь на преобразовании двоичных чисел в десятичные). Зачем это нужно, если можно просто использовать %2? На моем компьютере, например, &1 выполняется на 66% быстрее. Довольно неплохое повышение производительности, скажу я вам.

Исключающее ИЛИ (XOR)

Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:

Например, выражение 138^43 будет равно…

… 10100001₂ , или 160₁₀

С помощью ^ можно поменять значения двух переменных (имеющих одинаковый тип данных) без использования временной переменной.

Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:

String msg = "This is a message";
char[] message = msg.toCharArray();
String key = ".*)";
String encryptedString = new String();
for(int i = 0; i< message.length; i++){
   encryptedString += message[i]^key.toCharArray()[i%key.length()];
}

Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.

Побитовое отрицание (NOT)

Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.

Вот, например, операция ~52:

Результатом будет 203₁₀

При использовании побитового отрицания знак результата всегда будет противоположен знаку исходного числа (при работе со знаковыми числами). Почему так происходит, узнаете прямо сейчас.

Дополнительный код

Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.

Главное, что вам нужно знать о числах, записанных в дополнительном коде — это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 — то оно отрицательное. То есть, 10111101 — отрицательное число, а 01000011 — положительное.

Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.

Например, если мы имеем 109:

Представленным выше методом мы получаем -109 в дополнительном коде.
Только что было представлено очень упрощенное объяснение дополнительного кода, и я настоятельно советую вам детальнее изучить эту тему.

Побитовый сдвиг влево

Побитовые сдвиги немного отличаются от рассмотренных ранее битовых операций. Побитовый сдвиг влево сдвигает биты своего операнда на N количество битов влево, начиная с младшего бита. Пустые места после сдвига заполняются нулями. Происходит это так:

Интересной особенностью сдвига влево на N позиций является то, что это эквивалентно умножению числа на 2^N. Таким образом, 43<<4 == 43*Math.pow(2,4). Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.

Побитовый сдвиг вправо

Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.

Если операнд положительный, то пустые места заполняются нулями. Если же изначально мы работаем с отрицательным числом, то все пустые места слева заполняются единицами. Это делается для сохранения знака в соответствии с дополнительным кодом, объясненным ранее.

Так как побитовый сдвиг вправо — это операция, противоположная побитовому сдвигу влево, несложно догадаться, что сдвиг числа вправо на N количество позиций также делит это число на 2^N. Опять же, это выполняется намного быстрее обычного деления.

Вывод

Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.

Источники: «Understanding Bitwise Operators»,
«How to program with Bitwise Operators: The House with 8 Doors»,
«Understand how bitwise operators work».

Двоичная математика, работа с битовой логикой

Наряду с обычными логическими операция над логическими типами Boolean, часто приходится выполнять операции и над отдельными битами, обычно используемыми, как флаги. Для эффективной работы необходимо понимание логических операций.

Паскаль поддерживает следующие логические операции

· AND – логическое И;

· OR — (включающие) логическое ИЛИ;

· XOR — (исключающие) логическое ИЛИ;

· NOT — отрицание или инверсия бита;

· SHL – логический сдвиг влево;

· SHR – логический сдвиг вправо.

Другие логические операции над числами в Паскаль не включены, но доступны через ассемблерные вставки.

Каждый бит может иметь только два состояния ЛОЖЬ (FALSE) или ИСТИНА (TRUE)

Состояние бита можно описывать и другими словами, часть которых пришла из математики, часть из электроники, часть из логики.

Для значения ЛОЖЬ, альтернативные варианты такие – НЕТ, НОЛЬ, ВЫКЛЮЧЕНО, НЕ УСТАНОВЛЕНО, СБРОШЕНО, FALSE, F, 0, — и другие.

Для значения ИСТИНА, альтернативные варианты такие – ДА, ЕДИНИЦА, ВКЛЮЧЕНО, УСТАНОВШЕНО, ВЗВЕДЕНО, TRUE, T, 1, + и другие.

Рассмотрим эти операции по отдельности

AND – логическое И, эта операции выглядит так

Выражение истинно, когда истинны оба бита. Присказка «И там И там»

OR — (включающие) логическое ИЛИ, эта операции выглядит так

Выражение истинно, когда истинен хотя бы один бит. Присказка «ИЛИ там ИЛИ там, включая и там и там»

XOR — (исключающие) логическое ИЛИ, эта операции выглядит так

Выражение истинно, когда истинен только один бит. Присказка «ИЛИ там ИЛИ там, исключая и там и там»

NOT — отрицание или инверсия бита, эта операции применяется только к одному биту, действие простое текущее значение бита изменяется на противоположное

SHL – логический сдвиг влево, операции применяется только к группе битов, одного из целочисленных типов Паскаля, например к байту, слову и т.д.

Сдвиг байта влево на один разряд.

Сдвиг байта влево на два разряда.

Байт смещается влево на один или более разрядов, позиции справа замещаются нулями, позиции слева теряются.

SHR – логический сдвиг вправо, операции применяется только к группе битов, одного из целочисленных типов Паскаля, например к байту, слову и т.д.

Сдвиг байта вправо на один разряд.

Сдвиг байта вправо на два разряда.

Байт смещается вправо на один или более разрядов, позиции слева замещаются нулями, позиции справа теряются.

На этом описание операций заканчивается, и переходим к практическим примерам. Но вначале немного слов о нотации

Применяемая нотация при отображении чисел в литературе

Числа в символьной форме принято отображать, так что бы младшие разряды были справа, а строки слева, при этом если используется выравнивание, то оно тоже подчиняется этим правилам.

Нумерация разрядов начинается с нуля в соответствии со степень разряда и описывается формулой K*M^N, где K это коэффициент в диапазоне от 0 до M-1, M это основание числа, а N это степень. Число в степени 0 для всех оснований равно 1.

Посмотрим на примере следующей таблицы для четырех основных оснований.

Для числа 100

Для числа 123

Практические примеры

В начале несколько простых примеров по использованию логических операций, а в заключение будет рассмотрено применение этих приемов для работы с каталогами.

Получение позиции бита или его значения

1 shl N

В данном примере единица сдвигается влево на нужное количество разрядов, и в результате получаем двоичное значение, равное 2^N, где в установлен один единственный бит, соответствующий разряду числа. Этот прием может использоваться с переменной для расчета позиции во время выполнения или во время компиляции, во втором случае код генерироваться не будет, а компилятор просто рассчитает значение и подставит его в программу, не генерируя дополнительного кода. Это удобно для указания номера бита, не представляя его в виде десятичной или шестнадцатеричной константы. Но чаще бывает удобнее использовать именованные константы, поскольку они более информативны, примеры этого будут приведены в конце статьи.

Установка бита

Для установки отдельного бита или группы битов используется операция ИЛИ, использование иллюстрируется ниже приведенным кодом в виде отдельной функции и результатом выполнения в виде таблицы.

function SetBit(Src: Integer; bit: Integer): Integer;

begin

  Result := Src or (1 shl Bit);

end;

Здесь происходит следующее:

Сначала мы рассчитываем позицию бита – (1 shl Bit), затем устанавливаем полученный бит и возвращаем результат через предопределенную переменную Result.

Пример использования:

DummyValue := SetBit(DummyValue, 2);

Как видим, вне зависимости от начального состояние бита, после выполнения операции бит становится равны единице.

Сброс бита

Для сброса отдельного бита или группы битов используется операция И совместно с инверсной маской, использование иллюстрируется ниже приведенным кодом в виде отдельной функции и результатом выполнения в виде таблицы.

function ResetBit(Src: Integer; bit: Integer): Integer;

begin

  Result := Src and not (1 shl Bit);

end;

Здесь происходит следующее:

Сначала мы рассчитываем позицию бита – (1 shl Bit), затем с помощью операции NOT инвертируем полученную маску, устанавливая, не затрагиваемые биты маски в единицу, а затрагиваемый бит в ноль, затем сбрасываем этот бит, а результат возвращаем результат через предопределенную переменную Result.

Пример использования:

DummyValue := ResetBit(DummyValue, 2);

Как видим, вне зависимости от начального состояние бита, после выполнения операции бит становится равны нулю.

Переключение бита

Для переключения отдельного бита или группы битов используется операция исключающие ИЛИ, использование иллюстрируется ниже приведенным кодом в виде отдельной функции и результатом выполнения в виде таблицы.

function InvertBit(Src: Integer; bit: Integer): Integer;

begin

  Result := Src xor (1 shl Bit);

end;

Здесь происходит следующее:

Сначала мы рассчитываем позицию бита – (1 shl Bit), затем с помощью операции XOR переключаем бит, а результат возвращаем результат через предопределенную переменную Result.

Пример использования:

DummyValue := InvertBit(DummyValue, 2);

Как видим, состояние бита B2 изменяется на противоположное.

Проверка бита

Для проверки бита используется операция AND и анализ результата на равенство нулю.

if Value and (1 shl N) <> 0 then ... установлен

if Value and (1 shl N) = 0 then ... не установлен

чаще всего это используется в другой форме, вместо расчета позиции используется именованная константа, например

const

  B2 = 4  // B2 (1 shl 2)

Begin

  if Value and B2 = B2 then ... установлен

  if Value and B2 = 0  then ... не установлен

end;

Это более наглядно, особенно если константе дано более значимое имя, чем B2, например, для проверки готовности передатчика мы можем определить константу с именем TxReady, тогда это будет выглядеть очень красиво.

const

  TxReady = 4 

Begin

  if Value and TxReady then begin

    ...  обработка готовности передатчика

  end;

end;

Ну, вот с базисом мы покончили и пора приступить к более полезным и практическим примерам. В качестве примера выберем поиск папок и файлов. Пример был разработан для FAQ конференции fido7.ru.delphi, в дальнейшем был немного модернизирован по замечаниям от Юрия Зотова. Полный пример и остальные статьи из FAQ доступны для загрузки с моего сайта.

procedure ScanDir(StartDir: string; Mask:string; List:TStrings);

var

  SearchRec : TSearchRec;

Begin

  if Mask = '' then Mask := '*.*';

  if StartDir[Length(StartDir)] <> '' then StartDir := StartDir + '';

  if FindFirst(StartDir + Mask, faAnyFile, SearchRec) = 0 then

  begin

    repeat

      Application.ProcessMessages;        

      if (SearchRec.Attr and faDirectory) <> faDirectory  

      then

        List.Add(StartDir + SearchRec.Name)

      else if (SearchRec.Name <> '..') and (SearchRec.Name <> '.')

      then  

      begin

        List.Add(StartDir + SearchRec.Name + '');

        ScanDir(StartDir + SearchRec.Name + '', Mask, List);

      end;

    until FindNext(SearchRec) <> 0;

    FindClose(SearchRec);

  end;

end;

Рассмотрим ключевые моменты, относящиеся к данной статье.

if FindFirst(StartDir + Mask, faAnyFile, SearchRec) = 0 then

Здесь является битовой маской, описанной в модуле SysUtils, ее значение равно $3F, она предназначена для включения в поиск специальных файлов и одновременно для изоляции лишних бит из структуры TSearchRec, отдельные биты данной маски описаны как именованные константы.

if (SearchRec.Attr and faDirectory) <> faDirectory  

здесь мы видим проверку флага faDirectory, работает это следующим образом, сначала изолируются не нужные биты, затем проводится проверка на неравенство нулю, поскольку все остальные биты изолированы, то возможны только два значения, ноль, если флаг не установлен и не ноль установлен, в зависимости от результата выполняется, или часть THEN, или часть ELSE. Других вещей касаемо нашей статьи в примере нет и поэтому рассматривать больше нечего. Прочие логические операции работают с булевыми, а не с битовыми значения.

В заключение статьи можно еще привести примеры использования масок для изоляции битов и выполнения операций над оставшимися битами, возьмем для примера какую ни будь абстрактную комбинацию бит и выполним, что ни будь с ними.

Например, у нас есть такая структура некоторого устройства, и при поступлении данных происходит прерывание, обработка которого поступает в наш обработчик и в другие вместе с кодом состояния, если мы обработали сообщение, то мы должны возвратить значение TRUE, если то FALSE и тогда управление будет передано следующему в цепочке обработчику. Бит TxReady проверять не надо, управление будет поступать, только тогда когда он установлен.

abcccddd – где

a – бит готовности

b – бит разрешения прерывания

ccc – тип операции

ddd – счетчик

function MyHandler(Code: byte): Boolean;

const

  TxReady     = $80;

  IntBit      = $40;

  TypeMask    = $38;

  CounterMask = $07;

var

  I: Integer;

  TypeBits: Byte;

begin

  if (Code and Intbit) = Intbit 

  then

  begin

    // изллируем биты типа и смещаем вправо для дальнейшей обработки

    TypeBits := (Code and TypeMask) shr 3; 

    Case TypeBits of

      0: begin

                        for I := 1 to (Code and CounterMask) do

            begin

              считываем N данных, количесво указано в битах CounterMask,

              которые мы изолировали и использовали в качестве значения 

              для окончания цикла.

            end;

            Result := TRUE; // обрабатали, пусть больше никто не трогает

         end;

      1: begin

           команда 1, что то делаем

           Result := TRUE; // обрабатали, пусть больше никто не трогает

         end;

      2: begin

           команда 2, что то делаем

           Result := TRUE; // обрабатали, пусть больше никто не трогает

         end;

      else Result := FALSE; // другие команды не наше дело

    end;

  end

  else

  begin

    Result := FALSE; // пусть другой обрабатывает

  end;

end;

Ошибки при работе с битами

Например, для сложения бит мы можем использовать два варианта или операцию + или операцию OR. Первый вариант является ошибочным.

AnyValue + 2, если бит два установлен, то в результате этой операции произойдет перенос в следующий разряд, а сам бит окажется сброшенным вместо его установки, так можно поступать если только если есть уверенность в результате, то если заранее известно начальное значение. А вот в случае использования варианта AnyValue or 2, такой ошибки не произойдет. Тоже относится к операции вычитания для сброса бита.

faAnyFiles – faDirectory ошибки не даст, а вот AnyFlags – AnyBit может, дать правильный вариант, а может нет. Зато AnyFlags and not AnyBit всегда даст то что замали, использования этой техники будет правильнее и для работы с аттрибутами файлов — faAnyFiles and not faDirectory. В качестве домашнего задания попробуйте выполнить это на бумаге для разных комбинацияй бит.

Еще одна распростаненая ошибка, это логическая при выполнении операций над групами бит. Например неверено выполнять операцию сравнения над следующей конструкцией AnyFlags and 5 <> 0, если истина должна быть при установке обеих бит, надо писать так AnyFlags and 5 = 5, зато если устраивает истина при установке любого из бит, выражение AnyFlags and 5 <> 0 будет верныи.

На этом статья закончена и вы смогли получить начальные сведения по выполнению логических операций с битами, в заключении приведу и таблицу весовых коэффициентов, чтобы было легче рассчитывать константы.

Приложения

Таблица весовых множителей для 32 битного числа