std/bitops

Этот модуль реализует ряд методов низкого уровня для работы с битами.

По умолчанию, там, где это возможно, используются встроенные функции компилятора для повышения производительности на поддерживаемых компиляторах: GCC, LLVM_GCC, CLANG, VCC, ICC.

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

Этот модуль также совместим с другими бэкендами: JavaScript, NimScript а также с compiletime VM.

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

В настоящее время только fastLog2, firstSetBit, countLeadingZeroBits и countTrailingZeroBits могут возвращать неопределённые и/или зависящие от платформы значения, если предоставлены некорректные входные данные.

Импорты

macros, since, bitops_utils, countbits_impl

Типы

BitsRange[T] = range[0 .. sizeof(T) * 8 - 1]

Диапазон с всеми битами для типа T. Source Edit

Процедуры

func bitnot[T: SomeInteger](x: T): T {.magic: "BitnotI", ...raises: [], tags: [],
                                       forbids: [].}

Вычисляет bitwise complement целого числа x. Исходный код Редактировать

proc bitslice[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Изменяет v в извлечённый (и сдвинутый) срез битов из v.

Пример:

var x = 0b101110
x.bitslice(2 .. 4)
doAssert x == 0b011

Исходный код Редактировать

func bitsliced[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Возвращает извлечённый (и сдвинутый) срез битов из v.

Пример:

doAssert 0b10111.bitsliced(2 .. 4) == 0b101
doAssert 0b11100.bitsliced(0 .. 2) == 0b100
doAssert 0b11100.bitsliced(0 ..< 3) == 0b100

Исходный код Редактировать

proc clearBit[T: SomeInteger](v: var T; bit: BitsRange[T]) {.inline.}

Изменяет v, установив бит в позиции bit в 0.

Пример:

var v = 0b0000_0011'u8
v.clearBit(1'u8)
doAssert v == 0b0000_0001'u8

Исходный код Редактировать

proc clearMask[T: SomeInteger](v: var T; mask: T) {.inline.}

Изменяет v, установив все 1 биты с mask в 0.

Эффективно соответствует операции bitand с инвертированной маской.

Пример:

var v = 0b0000_0011'u8
v.clearMask(0b0000_1010'u8)
doAssert v == 0b0000_0001'u8

Исходный код Редактировать

proc clearMask[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Изменяет v, установив все 1 биты в диапазоне slice в 0.

Эффективно соответствует операции bitand с инвертированной маской.

Пример:

var v = 0b0000_0011'u8
v.clearMask(1 .. 3)
doAssert v == 0b0000_0001'u8

Исходный код Редактировать

func clearMasked[T: SomeInteger](v, mask: T): T {.inline.}

Возвращает v, установив все 1 биты с mask в 0.

Эффективно соответствует операции bitand с инвертированной маской.

Пример:

let v = 0b0000_0011'u8
doAssert v.clearMasked(0b0000_1010'u8) == 0b0000_0001'u8

Исходный код Редактировать

func clearMasked[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Возвращает v, установив все 1 биты в диапазоне slice в 0.

Эффективно соответствует операции bitand с инвертированной маской.

Пример:

let v = 0b0000_0011'u8
doAssert v.clearMasked(1 .. 3) == 0b0000_0001'u8

Исходный код Редактировать

func countLeadingZeroBits(x: SomeInteger): int {.inline.}

Возвращает количество старших нулевых битов в целом числе. Если x равно нулю, когда noUndefinedBitOpts установлено, результат равен 0, в противном случае результат не определён.

См. также:

• countTrailingZeroBits proc

Пример:

doAssert countLeadingZeroBits(0b0000_0001'u8) == 7
doAssert countLeadingZeroBits(0b0000_0010'u8) == 6
doAssert countLeadingZeroBits(0b0000_0100'u8) == 5
doAssert countLeadingZeroBits(0b0000_1000'u8) == 4
doAssert countLeadingZeroBits(0b0000_1111'u8) == 4

Исходный код Редактировать

func countSetBits(x: SomeInteger): int {.inline.}

Считает установленные биты в целое число (также называется весом Хэмминга).

Пример:

doAssert countSetBits(0b0000_0011'u8) == 2
doAssert countSetBits(0b1010_1010'u8) == 4

Исходный код Редактировать

func countTrailingZeroBits(x: SomeInteger): int {.inline.}

Возвращает количество концевых нулей в целом числе. Если x равно нулю, когда noUndefinedBitOpts установлено, результат равен 0, в противном случае результат не определён.

См. также:

• countLeadingZeroBits proc

Пример:

doAssert countTrailingZeroBits(0b0000_0001'u8) == 0
doAssert countTrailingZeroBits(0b0000_0010'u8) == 1
doAssert countTrailingZeroBits(0b0000_0100'u8) == 2
doAssert countTrailingZeroBits(0b0000_1000'u8) == 3
doAssert countTrailingZeroBits(0b0000_1111'u8) == 0

Исходный код Редактировать

func fastLog2(x: SomeInteger): int {.inline.}

Быстро находит логарифм по основанию 2 целого числа. Если x равно нулю, когда noUndefinedBitOpts установлено, результат равен -1, в противном случае результат не определён.

Пример:

doAssert fastLog2(0b0000_0001'u8) == 0
doAssert fastLog2(0b0000_0010'u8) == 1
doAssert fastLog2(0b0000_0100'u8) == 2
doAssert fastLog2(0b0000_1000'u8) == 3
doAssert fastLog2(0b0000_1111'u8) == 3

Исходный код Редактировать

func firstSetBit(x: SomeInteger): int {.inline.}

Возвращает индекс (с учётом 1) наименее значащего установленного бита x. Если x равно нулю, когда noUndefinedBitOpts установлено, результат равен 0, в противном случае результат не определён.

Пример:

doAssert firstSetBit(0b0000_0001'u8) == 1
doAssert firstSetBit(0b0000_0010'u8) == 2
doAssert firstSetBit(0b0000_0100'u8) == 3
doAssert firstSetBit(0b0000_1000'u8) == 4
doAssert firstSetBit(0b0000_1111'u8) == 1

Исходный код Редактировать

proc flipBit[T: SomeInteger](v: var T; bit: BitsRange[T]) {.inline.}

Изменяет v, инвертируя бит в позиции bit.

Пример:

var v = 0b0000_0011'u8
v.flipBit(1'u8)
doAssert v == 0b0000_0001'u8

v = 0b0000_0011'u8
v.flipBit(2'u8)
doAssert v == 0b0000_0111'u8

Исходный код Редактировать

proc flipMask[T: SomeInteger](v: var T; mask: T) {.inline.}

Изменяет v, инвертируя все 1 биты с mask.

Эффективно соответствует операции bitxor.

Пример:

var v = 0b0000_0011'u8
v.flipMask(0b0000_1010'u8)
doAssert v == 0b0000_1001'u8

Исходный код Редактировать

proc flipMask[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Изменяет v, инвертируя все 1 биты в диапазоне slice.

Эффективно соответствует операции bitxor.

Пример:

var v = 0b0000_0011'u8
v.flipMask(1 .. 3)
doAssert v == 0b0000_1101'u8

Исходный код Редактировать

func flipMasked[T: SomeInteger](v, mask: T): T {.inline.}

Возвращает v, инвертируя все 1 биты с mask.

Эффективно соответствует операции bitxor.

Пример:

let v = 0b0000_0011'u8
doAssert v.flipMasked(0b0000_1010'u8) == 0b0000_1001'u8

Исходный код Редактировать

func flipMasked[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Возвращает v, инвертируя все 1 биты в диапазоне slice.

Эффективно соответствует операции bitxor.

Пример:

let v = 0b0000_0011'u8
doAssert v.flipMasked(1 .. 3) == 0b0000_1101'u8

Исходный код Редактировать

proc mask[T: SomeInteger](v: var T; mask: T) {.inline.}

Изменяет v, при этом только биты 1 из mask совпадающие с битами v устанавливаются в 1.

Эффективно соответствует операции bitand.

Пример:

var v = 0b0000_0011'u8
v.mask(0b0000_1010'u8)
doAssert v == 0b0000_0010'u8

Исходный код Изменить

proc mask[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Изменяет v, при этом только биты 1 в диапазоне slice совпадающие с битами v устанавливаются в 1.

Эффективно соответствует операции bitand.

Пример:

var v = 0b0000_1011'u8
v.mask(1 .. 3)
doAssert v == 0b0000_1010'u8

Исходный код Изменить

proc masked[T: SomeInteger](v, mask: T): T {.inline.}

Возвращает v, при этом только биты 1 из mask совпадающие с битами v устанавливаются в 1.

Эффективно соответствует операции bitand.

Пример:

let v = 0b0000_0011'u8
doAssert v.masked(0b0000_1010'u8) == 0b0000_0010'u8

Исходный код Изменить

func masked[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Возвращает v, при этом только биты 1 в диапазоне slice совпадающие с битами v устанавливаются в 1.

Эффективно соответствует операции bitand.

Пример:

let v = 0b0000_1011'u8
doAssert v.masked(1 .. 3) == 0b0000_1010'u8

Исходный код Изменить

func parityBits(x: SomeInteger): int {.inline.}

Вычисление чётности бита в целом числе. Если количество битов 1 нечётное, чётность равна 1, иначе 0.

Пример:

doAssert parityBits(0b0000_0000'u8) == 0
doAssert parityBits(0b0101_0001'u8) == 1
doAssert parityBits(0b0110_1001'u8) == 0
doAssert parityBits(0b0111_1111'u8) == 1

Исходный код Изменить

func popcount(x: SomeInteger): int {.inline.}

Псевдоним для countSetBits (вес Хэмминга). Исходный код Изменить

func reverseBits[T: SomeUnsignedInt](x: T): T

Возвращает обращение битов x.

Пример:

doAssert reverseBits(0b10100100'u8) == 0b00100101'u8
doAssert reverseBits(0xdd'u8) == 0xbb'u8
doAssert reverseBits(0xddbb'u16) == 0xddbb'u16
doAssert reverseBits(0xdeadbeef'u32) == 0xf77db57b'u32

Исходный код Изменить

func rotateLeftBits[T: SomeUnsignedInt](value: T;
                                        shift: range[0 .. (sizeof(T) * 8)]): T {.
    inline.}

Циклический сдвиг влево битов в value.

Пример:

doAssert rotateLeftBits(0b0110_1001'u8, 4) == 0b1001_0110'u8
doAssert rotateLeftBits(0b00111100_11000011'u16, 8) ==
  0b11000011_00111100'u16
doAssert rotateLeftBits(0b0000111111110000_1111000000001111'u32, 16) ==
  0b1111000000001111_0000111111110000'u32
doAssert rotateLeftBits(0b00000000111111111111111100000000_11111111000000000000000011111111'u64, 32) ==
  0b11111111000000000000000011111111_00000000111111111111111100000000'u64

Исходный код Изменить

func rotateRightBits[T: SomeUnsignedInt](value: T;
    shift: range[0 .. (sizeof(T) * 8)]): T {.inline.}

Циклический сдвиг вправо битов в value.

Пример:

doAssert rotateRightBits(0b0110_1001'u8, 4) == 0b1001_0110'u8
doAssert rotateRightBits(0b00111100_11000011'u16, 8) ==
  0b11000011_00111100'u16
doAssert rotateRightBits(0b0000111111110000_1111000000001111'u32, 16) ==
  0b1111000000001111_0000111111110000'u32
doAssert rotateRightBits(0b00000000111111111111111100000000_11111111000000000000000011111111'u64, 32) ==
  0b11111111000000000000000011111111_00000000111111111111111100000000'u64

Исходный код Изменить

proc setBit[T: SomeInteger](v: var T; bit: BitsRange[T]) {.inline.}

Изменяет v, устанавливая бит в позиции bit в 1.

Пример:

var v = 0b0000_0011'u8
v.setBit(5'u8)
doAssert v == 0b0010_0011'u8

Исходный код Изменить

proc setMask[T: SomeInteger](v: var T; mask: T) {.inline.}

Изменяет v, устанавливая все биты 1 из mask в 1.

Эффективно соответствует операции bitor.

Пример:

var v = 0b0000_0011'u8
v.setMask(0b0000_1010'u8)
doAssert v == 0b0000_1011'u8

Исходный код Изменить

proc setMask[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Изменяет v, устанавливая все биты 1 в диапазоне slice в 1.

Эффективно соответствует операции bitor.

Пример:

var v = 0b0000_0011'u8
v.setMask(2 .. 3)
doAssert v == 0b0000_1111'u8

Исходный код Изменить

func setMasked[T: SomeInteger](v, mask: T): T {.inline.}

Возвращает v, устанавливая все биты 1 из mask в 1.

Эффективно соответствует операции bitor.

Пример:

let v = 0b0000_0011'u8
doAssert v.setMasked(0b0000_1010'u8) == 0b0000_1011'u8

Исходный код Изменить

func setMasked[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Возвращает v, устанавливая все биты 1 в диапазоне slice в 1.

Эффективно соответствует операции bitor.

Пример:

let v = 0b0000_0011'u8
doAssert v.setMasked(2 .. 3) == 0b0000_1111'u8

Исходный код Изменить

proc testBit[T: SomeInteger](v: T; bit: BitsRange[T]): bool {.inline.}

Возвращает true, если бит в v в позиции bit равен 1.

Пример:

let v = 0b0000_1111'u8
doAssert v.testBit(0)
doAssert not v.testBit(7)

Исходный код Изменить

func toMask[T: SomeInteger](slice: Slice[int]): T {.inline.}

Создаёт битовую маску на основе слайса битов.

Пример:

doAssert toMask[int32](1 .. 3) == 0b1110'i32
doAssert toMask[int32](0 .. 3) == 0b1111'i32

Исходный код Изменить

Макросы

macro bitand[T: SomeInteger](x, y: T; z: varargs[T]): T

Вычисляет bitwise and всех аргументов коллективно. Исходный код Изменить

macro bitor[T: SomeInteger](x, y: T; z: varargs[T]): T

Вычисляет bitwise or всех аргументов коллективно. Исходный код Изменить

macro bitxor[T: SomeInteger](x, y: T; z: varargs[T]): T

Вычисляет bitwise xor всех аргументов коллективно. Исходный код Изменить

macro clearBits(v: typed; bits: varargs[typed]): untyped

Изменяет v, устанавливая биты в позициях bits в 0.

Пример:

var v = 0b1111_1111'u8
v.clearBits(1, 3, 5, 7)
doAssert v == 0b0101_0101'u8

Исходный код Изменить

macro flipBits(v: typed; bits: varargs[typed]): untyped

Изменяет v, устанавливая биты в позициях bits в 0.

Пример:

var v = 0b0000_1111'u8
v.flipBits(1, 3, 5, 7)
doAssert v == 0b1010_0101'u8

Исходный код Изменить

macro setBits(v: typed; bits: varargs[typed]): untyped

Изменяет v, устанавливая биты в позициях bits в 1.

Пример:

var v = 0b0000_0011'u8
v.setBits(3, 5, 7)
doAssert v == 0b1010_1011'u8

Исходный код Изменить