Трюки из C в D

В этой небольшой статье я расскажу, как при помощи некоторых очевидных и не очень способах, часто применяемых в языке программирования C, сделать что-нибудь с некоторыми (в основном, числовыми) значениями.

Проверка числа на четность / нечетность

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

x % 2 == 0

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

!(x & 1)

а для проверки на нечетность достаточно применить вот такой прием:

x & 1

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

Приведение любого типа к bool

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

cast(bool) x

Но, операция используемая в таком решении не всегда безопасна, и порой требуется от нее отказаться. В этом случае к нам приходит на помощь, такая операция как отрицание ! — дело в том, что любое «ненулевое» значение компилятор трактует как true (если это значение используется в условиях и циклам по условиям), а «нулевое значение» трактуется как false. При этом, для типа T величина, определяемая свойством T.init гарантировано интерпретируется компилятором, как false.

Таким образом, можно применить следующее экстраординарное выражение:

!!x

Думаю, вы поняли, как оно понимается компилятором.

Является ли число степенью двойки

Подобная задача решается самыми разными способами: от банальной сверки с таблицей степеней до приемов со скоростным логарифмированием по основанию 2, но все-таки есть один неочевидный трюк:

(n - 1) & n

Скоростное умножение/деление на 2

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

Когда-то, еще в начале компьютерной эры, быстродействие компьютеров оставляло желать лучшего и именно тогда был придуман трюк, позволяющий по быстрому множить или разделить на 2: для умножения на 2 достаточно сдвинуть целое число на 1 разряд влево (<<), а для обратной операции необходимо выполнить сдвиг на одну позицию вправо (>>).

Кроме того, сдвиг влево или вправо на N ячеек позволяет сделать умножение или деление на 2 в степени N.

Секрет прост: в набор инструкций современных процессоров встроены атомарные операции для проведения сдвига.

Битовые маски

Допустим у вас есть некоторое значение, для которого необходимо узнать, какое значение имеет его N-ый бит. В D есть тип byte, но нет типа bit (хотя раньше был…), что делать ?

Для выяснения того, какое значение принимает N-ый бит числа, лучше всего воспользоваться побитовым «И», которое сопоставляет соответствующие биты некоторых двух чисел.

Предположим, у нас есть число 147, а нужно выяснить какое значение (0 или 1) принимает 5-ый бит этого числа: для этого мы воспользуемся приемом, который называется наложением битовой маски. Наложение маски, заключается в следующем — берем исходное число и некоторое другое число (которое и называется битовой маской), которое будет служить своеобразным шаблоном для сопоставления по битам, и применяем к этим числам побитовое «И».

Если вспомнить, таблицу истинности «И» то мы увидим, что для двух значений мы получим истину (т.е. единицу, если в числовой интерпретации) только в том случае, если оба значения истинны. Таким образом, зная , что исходное число мы изменять не вправе и именно из него мы будем выделять значение нужного бита, мы придем к выводу, что второе число (битовую маску) мы должны сформировать таким образом, чтобы в ее двоичном представлении на нужном месте (которое по номеру соответствует выделяемому биту) стояла 1, а в остальных местах (разрядах двоичного представления) был ноль.

Возвращаясь к нашему примеру выделения 5-ого бита из 147, приходим к выводу, что первое число — это 147 (в двоичном виде выглядит как 10010011), а второе число в двоичном виде выглядит примерно так: 00010000 (прошу заметить, что число двоичных разрядов в битовой маске равно количеству двоичных разрядов в исходном числе). Таким образом выделение 5-ого бита выглядит так:

147 & 0b00010000

и при этом происходит следующее:

&	Число	1	1	1	1
	Битовая маска	0	1	0	0
	Результат	0	1	0	0

и получается результат — 00010000, что соответствует числу 16 в десятеричной системе счисления. Если вспомнить степени двойки, 2 в 4 степени равно 16 (дело в том, что нумерация битов начинается с правого конца и с нуля, в нашем случае: отсчет был начать с правого конца, но с единицы; а потому степень равна 4 (5 — 1), не 5, как следовало ожидать).

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

А что если нам нужно, не узнать какие биты в числе установлены, а установить их?

В этом случае, нам способна помочь такая операция, как побитовое «ИЛИ», обозначаемая в D, как |. При этом, все выглядит также, как и в случае, с побитовым «И», возьмем и установим 5 бит в числе 147 в 1, для чего воспользуемся следующим приемом:

147 | 0b00010000

Ну и в виде таблицы это выглядит так:

\|	Число	1	1	1	1
	Битовая маска	0	1	0	0
	Результат	1	1	1	1

Побитовое «ИЛИ» лишь устанавливает биты, но чтобы сбросить бит (т.е установить его в 0), потребуется применить побитовое «И», что явным образом следует из его таблицы истинности (ну а для побитового «ИЛИ» характерно следующее правило: если хотя бы один из битов равен 1, то результатом также будет 1).

Еще одной интересной операцией, является побитовое отрицание или побитовое «НЕ», которое уже описывалось выше. Эта операция проста и бесхитростна — инвертирует (заменяет 0 на 1, а 1 на 0) все биты некоего числа, что бывает очень удобно как в условиях, так и само по себе.

Помимо таких простых форм, которые описаны выше, битовые операции можно применять и не в прямом виде, когда битовая маска задается в виде двоичного числа, а в несколько ином виде (который более популярен), когда битовая маска задается шестнадцатеричным числом (числа с префиксом 0x в D). Такая форма применения снискала свою популярность из-за более легкого восприятия (что, конечно, не отменяет необходимости подумать над составлением маски) и из-за того, что двоичное число легко (прямо по внешнему виду) переводится в шестнадцатеричное с помощью принципа тетрад: каждая четверка двоичных цифр соответствует одной шестнадцатеричной цифре:

Десятичная цифра	Двоичная тетрада	Шестнадцатеричная цифра
0	0000	0
1	0001	1
2	0010	2
3	0011	3
4	0100	4
5	0101	5
6	0110	6
7	0111	7
8	1000	8
9	1001	9
10	1010	A
11	1011	B
12	1100	C
13	1101	D
14	1110	E
15	1111	F

Например, число 0b11000100 легко переводится в 0xC4.

Применение исключающего ИЛИ

Исключающее «ИЛИ» или XOR довольно часто используется и также является одной из битовых операций. Таблица истинности для XOR, который в D обозначается как ^:

Первый операнд	Второй операнд	Результат
0	0	0
0	1	1
1	0	1
1	1	0

Или, если говорить упрощенно, то операция ^ возвращает 0 в том случае, если операнды одинаковые и 1, в том случае, если операнды разные.

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

void main()
{
	import std.stdio;
	
	int x = 5;
	int y = 7;
	
        x ^= y;
	y ^= x;
	x ^= y;

	writeln(x, " ", y);
}

Второе занимательное применение исключающего «ИЛИ» — реализация простейшего шифра, для чего используется занимательное свойство этой операции (оно же используется и в реализации обмена):

(a ^ k) ^ k == a;

где, a — бит исходной последовательности, k — бит ключа.

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

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

Размер массива в старом стиле

Этот способ довольно часто применяется в языках типа C/C++, но в D применение этого способа неоправданно, в виду наличия метода length у статических массивов. Однако, этот способ зачастую имеет смысл при прямом использовании C-кода в D приложениях и для того, чтобы узнать сколько в массиве элементов можно применить следующий код:

void main()
{
	import std.stdio;

	float[5] tmp;
	writeln(tmp.sizeof / float.sizeof);
}

Быстрый обратный квадратный корень

Ребята, а теперь адская жесть: вычисление быстрого обратного корня с помощью метода Ньютона на C, при этом код был портирован из реальных исходников игры Quacke 3.

Тут, как говорится, без комментариев:

extern(C)
{
	float Q_rsqrt(float number)
	{
		long i;
		float x2, y;
		const float threehalfs = 1.5F;
		
		x2 = number * 0.5F;
		y = number;
		i = *(cast(long*) &y); // дьявольский хакинг на битовом уровне для чисел с плавающей точкой
		i = 0x5f3759df - (i >> 1); // что за хуйня ?
		y = *(cast(float*) &i);
		y = y * (threehalfs - (x2 * y * y)); // 1-ая итерация
		y = y * (threehalfs - (x2 * y * y)); // 2-ая итерация
		
		return y;
	}
}

Проверка отрицательности числа

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

Итак, проверка является ли некоторое число отрицательным, глубокий C Style.

Оригинал:

Версия на D:

extern(C)
{
	import core.stdc.stdlib;
	import core.stdc.stdio;
	
	static int isNegative(float arg)
	{
		char* p = cast(char*) malloc(20);
		sprintf(p, "%f", arg);
		return p[0] == '-';
	}
}

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

Заключение

Используйте приемы из C в D грамотно, но лучше, если вы будете использовать нативные средства D.

И, пожалуйста, не пытайтесь применять описанное из последних двух примеров в своем коде на D.