В этом скромном рецепте мы предлагаем вам некоторые функции, которые потенциально могут облегчить вам программирование, если вы вдруг будете работать со значениями как с наборами битов. К сожалению, в рецепте практически нет ничего оригинального, и большая часть реализации взята из одной очень интересной библиотеки для Python 3, но это не значит, что в изложенном нами нет полезных решений…
Итак, если вы вдруг нуждаетесь в какой-то процедуре работы с побитовыми операциями, то любезно предлагаем вам ознакомиться с тем, что мы собрали в данной скромной статье.
Без лишних слов, предлагаем вам код обобщенных функций (с комментариями) для некоторых операций с битами:
// дополнение до 2 auto twoComplement(T)(T n, T bits) { return ((cast(T) 1 << bits) - n) % (cast(T) 1 << bits); } // дополнение до 1 auto oneComplement(T)(T n, T bits) { return (cast(T) 1 << bits) - n - cast(T) 1; } // подсчет количества установленных в единицу бит auto countBits(T)(T n) { T count; if (n == 0) { count++; } else { while (n != 0) { n >>= 1; count++; } } return count; } // установить нужный бит в единицу auto setBit(T)(T n, T i) { return n | (cast(T) 1 << i); } // получить значение нужного бита auto getBit(T)(T n, T i) { return (n >> i) & cast(T) 1; } // переключить нужный бит auto toggleBit(T)(T n, T i) { return n ^ (cast(T) 1 << i); } // сбросить необходимый бит auto unsetBit(T)(T n, T i) { return (n | (cast(T) 1 << i)) ^ (cast(T) 1 << i); } // создать битовую маску (n - количество единиц, k - количество последующих за ними нулей) auto createMask(T)(T n, T k) { return ((cast(T) 1 << n) - cast(T) 1) << k; } // извлечь биты (смысл k и n как и в предыдущем случае) auto extractBitField(T)(T x, T n, T k) { return (x & createMask(n, k)) >> k; } // номер последнего установленного бита auto lastSettedBit(T)(T n) { return countBits(n) - cast(T) 1; } // номер последнего сброшенного в ноль бита auto lastUnsettedBit(T)(T n) { return lastSettedBit( oneComplement( n, countBits(n) ) ); } // количество нулевых бит в конце числа) auto countTrailingZeroes(T)(T n) { if (n == 0) { return 0; } else { return countBits(n & (-n)) - cast(T) 1; } } // удалить нули в конце числа auto removeTrailingZeroes(T)(T n) { if (n == 0) { return 0; } else { return n >> countTrailingZeroes(n); } } // догарифм по основанию два с округлением в большую сторону auto ceilLog2(T)(T n) { T x = lastSettedBit(n); return x + cast(T) (n != (cast(T) 1 << x)); } // логарифм по основанию два с округлением в меньшую сторону auto floorLog2(T)(T n) { return countBits(n) - cast(T) 1; } // следующая степень двойки близкая к заданному числу auto nextPowerOfTwo(T)(T n) { return cast(T) 1 << ceilLog2(n); } // выравнивание двух значений auto alignValues(T, S)(T a, S b) { auto lengthA = countBits(a); auto lengthB = countBits(b); if (lengthA > lengthB) { b <<= (lengthA - lengthB); } else { if (lengthA < lengthB) { a <<= lengthB - lengthA; } } auto trailingA = countTrailingZeroes(a); auto trailingB = countTrailingZeroes(b); a >>= min(trailingA, trailingB); b >>= min(trailingA, trailingB); return tuple(a, b); }
Примечание автора. Если вдруг вам доведется применять эти операции с целыми числовыми типами в D (данные функции не работают с дробными типами, но при этом срабатывают на символьных, к примеру на char), то внимательно отслеживайте проделываемые операции. Дело в том, что иногда операции сдвига (и подобные им) делают так, что число «съезжает», т.е. сдвиговая операция предполагает расширение типа на значение большего размера (размер, разумеется в битах) — и вот тогда данный рецепт вам ничем не сможет помочь… К примеру, в практике одного из авторов блога, при использовании типа ulong произошел как раз такой случай: результат сдвига просто влево просто не помещается в ulong, и автора выручил несколько иной тип данных — BigInt из std.bigint (к сожалению, беззнаковый сдвиг вправо не поддерживается), но это было очень неудачное решение проблемы…
P.S: Мы не упоминаем наименование библиотеки на Python3 и не даем на нее ссылку, поскольку, это нарушит интригу одной из последующих статей. Обещаем, что в этой (одной из следующих) статье мы обязательно укажем ссылку на библиотеку и упомянем ее название.