Trait bitwise::Word [−] [src]

pub trait Word: Sized + Copy + Not<Output=Self> + BitOr<Output=Self> + BitXor<Output=Self> + Add<Output=Self> + Sub<Output=Self> + Mul<Output=Self> + Div<Output=Self> + Shr<u32, Output=Self> + Shl<u32, Output=Self> + BitAnd<Output=Self> + Eq + PartialOrd {
    type Signed: Word;
    type Unsigned: Word;
    fn size() -> usize;
    fn to_unsigned(self) -> Self::Unsigned;
    fn to_signed(self) -> Self::Signed;
    fn zero() -> Self;
    fn one() -> Self;
    fn two() -> Self;
    fn count_zeros(self) -> usize;
    fn count_ones(self) -> usize;
    fn leading_zeros(self) -> usize;
    fn trailing_zeros(self) -> usize;
    fn shift_logical_left(self, n: u32) -> Self;
    fn shift_logical_right(self, n: u32) -> Self;
    fn shift_arithmetic_left(self, n: u32) -> Self;
    fn shift_arithmetic_right(self, n: u32) -> Self;
    fn rotate_left(self, n: u32) -> Self;
    fn rotate_right(self, n: u32) -> Self;
    fn swap_bytes(self) -> Self;
    fn from_be(x: Self) -> Self;
    fn from_le(x: Self) -> Self;
    fn to_be(self) -> Self;
    fn to_le(self) -> Self;
    fn pow(self, exp: u32) -> Self;
    fn reverse_bit_groups(self, subword_bits: u32, group_subwords: u32) -> Self;
    fn set_bit_to(self, bit: u32, value: bool) -> Self;
    fn clear_bits_geq(self, bit: u32) -> Self;
    fn is_aligned(self, alignment: u32) -> bool;
    fn align_up(self, alignment: u32) -> Self;
    fn align_down(self, alignment: u32) -> Self;
    fn outer_perfect_shuffle(self) -> Self;
    fn outer_perfect_unshuffle(self) -> Self;
    fn scatter_bits(self, mask_: Self) -> Self;
    fn gather_bits(self, mask_: Self) -> Self;
    fn gather_bit_range(self, first: u32, length: u32) -> Self;
    fn morton_encode_2d(x: [Self; 2]) -> Self;
    fn morton_encode_3d(x: [Self; 3]) -> Self;
    fn morton_decode_2d(self) -> [Self; 2];
    fn morton_decode_3d(self) -> [Self; 3];

    fn bit_size() -> usize { ... }
    fn leading_ones(self) -> usize { ... }
    fn trailing_ones(self) -> usize { ... }
    fn and_not(self, y: Self) -> Self { ... }
    fn parity(self) -> usize { ... }
    fn next_abs_greater_even(self) -> Self { ... }
    fn prev_abs_smaller_even(self) -> Self { ... }
    fn next_abs_greater_equal_even(self) -> Self { ... }
    fn prev_abs_smaller_equal_even(self) -> Self { ... }
    fn next_abs_greater_odd(self) -> Self { ... }
    fn prev_abs_smaller_odd(self) -> Self { ... }
    fn next_abs_greater_equal_odd(self) -> Self { ... }
    fn prev_abs_smaller_equal_odd(self) -> Self { ... }
    fn clear(self) -> Self { ... }
    fn clear_least_significant_one(self) -> Self { ... }
    fn set_least_significant_zero(self) -> Self { ... }
    fn isolate_least_significant_one(self) -> Self { ... }
    fn isolate_least_significant_zero(self) -> Self { ... }
    fn clear_trailing_ones(self) -> Self { ... }
    fn set_trailing_zeros(self) -> Self { ... }
    fn mask_trailing_zeros(self) -> Self { ... }
    fn mask_trailing_ones(self) -> Self { ... }
    fn mask_trailing_zeros_and_least_significant_one(self) -> Self { ... }
    fn mask_trailing_ones_and_least_significant_zero(self) -> Self { ... }
    fn first_bit_set(self) -> usize { ... }
    fn first_bit_clear(self) -> usize { ... }
    fn reverse_bits(self) -> Self { ... }
    fn reverse_bit_pairs(self) -> Self { ... }
    fn reverse_bit_nibbles(self) -> Self { ... }
    fn reverse_byte_groups(self, bytes_per_block: u32, blocks_per_group: u32) -> Self { ... }
    fn reverse_bytes(self) -> Self { ... }
    fn set_bit(self, bit: u32) -> Self { ... }
    fn clear_bit(self, bit: u32) -> Self { ... }
    fn flip_bit(self, bit: u32) -> Self { ... }
    fn test_bit(self, bit: u32) -> bool { ... }
    fn clear_bits_leq(self, bit: u32) -> Self { ... }
    fn set_bits_geq(self, bit: u32) -> Self { ... }
    fn set_bits_leq(self, bit: u32) -> Self { ... }
    fn flip_bits_geq(self, bit: u32) -> Self { ... }
    fn flip_bits_leq(self, bit: u32) -> Self { ... }
    fn is_pow2(self) -> bool { ... }
    fn ceil_pow2(self) -> Self { ... }
    fn floor_pow2(self) -> Self { ... }
    fn average_floor(x: Self, y: Self) -> Self { ... }
    fn average_ceil(x: Self, y: Self) -> Self { ... }
    fn inner_perfect_shuffle(self) -> Self { ... }
    fn inner_perfect_unshuffle(self) -> Self { ... }
}

Bitwise manipulation algorithms for Words.

Note: this trat is not supposed to be implemented by library users. The distinction between functionality required and inherited has been arbitrarily placed at the boundary between "what is easier to implement within the trait" and "what is easier to implement with a macro" for the primitive integer types.

Associated Types

type Signed: Word

Signed Word Type of the same size as Self.

type Unsigned: Word

Unsigned Word Type of the same size as Self.

Required Methods

fn size() -> usize

Size of the word in bytes.

fn to_unsigned(self) -> Self::Unsigned

Transmutes the integer into an unsigned integer of the same size (bitwise loss-less).

Examples

use bitwise::Word;

assert_eq!((8i32).to_unsigned().to_signed(), 8i32);
assert_eq!((-1i32).to_unsigned().to_signed(), -1i32);

fn to_signed(self) -> Self::Signed

Transmutes an integer into a signed integer of the same size (bitwise loss-less).

Examples

use bitwise::Word;

assert_eq!((8i32).to_unsigned().to_signed(), 8i32);
assert_eq!((-1i32).to_unsigned().to_signed(), -1i32);

fn zero() -> Self

Returns a word with no bits set (an integer of value zero).

fn one() -> Self

Returns a word with the least significant bit set (an integer of value one).

fn two() -> Self

Returns a word with the second least significant bit set (an integer of value two).

fn count_zeros(self) -> usize

Returns the number of zeros in the binary representation of self.

Examples

use bitwise::Word;

let n = 0b0100_1100u8;

assert_eq!(n.count_zeros(), 5);

fn count_ones(self) -> usize

Returns the number of ones in the binary representation of self.

Keywords:

Population count, popcount, hamming weight, sideways sum.

Intrinsics:

  • ABM: popcnt.
  • SSE4.2: popcnt.
  • NEON: vcnt.
  • PowerPC: popcntb.
  • gcc/llvm builtin: __builtin_popcount(x).

Examples

use bitwise::Word;

let n = 0b0100_1100u8;

assert_eq!(n.count_ones(), 3);

fn leading_zeros(self) -> usize

Returns the number of leading zeros in the binary representation of self.

Keywords:

Count leading zeros.

Intrinsics:

  • ABM: lzcnt.
  • BMI 1.0: lzcnt.
  • ARMv5: clz.
  • PowerPC: cntlzd.
  • gcc/llvm builtin: x == 0 ? mem::size_of(x) * 8 : __builtin_clz(x).

Examples

use bitwise::Word;

let n = 0b0010_1000u16;

assert_eq!(n.leading_zeros(), 10);

fn trailing_zeros(self) -> usize

Returns the number of trailing zeros in the binary representation of self.

Keywords:

Count trailing zeros.

Intrinsics:

  • BMI 1.0: tzcnt.
  • gcc/llvm builtin: x == 0 ? mem::size_of(x) * 8 : __builtin_ctz(x).

Examples

use bitwise::Word;

let n = 0b0010_1000u16;

assert_eq!(n.trailing_zeros(), 3);

fn shift_logical_left(self, n: u32) -> Self

Shift the bits to the left by a specified amount, n.

Panics

If n > bit_size().

Examples

use bitwise::Word;

let a = 0b0000_1010u8;
let b = 0b0000_1001u8;

assert_eq!(a.shift_logical_left(4), 0b1010_0000u8);
assert_eq!(b.shift_logical_left(4), 0b1001_0000u8);
b.shift_logical_right((<u8 as Word>::bit_size() - 1) as u32);

fn shift_logical_right(self, n: u32) -> Self

Shift the bits to the right by a specified amount, n, with the high-order bits of the result cleared.

Panics

If n > bit_size().

Examples

use bitwise::Word;

let a = 0b0111_0000u8;
let b = 0b1001_0000u8;

assert_eq!(a.shift_logical_right(4), 0b0000_0111u8);
assert_eq!(b.shift_logical_right(4), 0b0000_1001u8);
b.shift_logical_right((<u8 as Word>::bit_size() - 1) as u32);

fn shift_arithmetic_left(self, n: u32) -> Self

Shift the bits to the left by a specified amount, n (same as shift_logical_left, provided for symmetry).

Panics

If n > bit_size().

Examples

use bitwise::Word;

let a = 0b0000_1010u8;
let b = 0b0000_1001u8;

assert_eq!(a.shift_arithmetic_left(4), 0b1010_0000u8);
assert_eq!(b.shift_arithmetic_left(4), 0b1001_0000u8);
b.shift_arithmetic_left((<u8 as Word>::bit_size() - 1) as u32);

fn shift_arithmetic_right(self, n: u32) -> Self

Shift the bits to the right by a specified amount, n, setting the high-order bits of the result to the value of the most significant bit of self.

Panics

If n > bit_size().

Examples

use bitwise::Word;

let a = 0b0111_0000u8;
let b = 0b1001_0000u8;

assert_eq!(a.shift_arithmetic_right(4), 0b0000_0111u8);
assert_eq!(b.shift_arithmetic_right(4), 0b1111_1001u8);
b.shift_arithmetic_right((<u8 as Word>::bit_size() - 1) as u32);

fn rotate_left(self, n: u32) -> Self

Shifts the bits to the left by a specified amount, n, wrapping the truncated bits to the end of the resulting integer.

Panics

If n > bit_size().

Examples

use bitwise::Word;

let n = 0x0123456789ABCDEFu64;
let m = 0x3456789ABCDEF012u64;

assert_eq!(n.rotate_left(12), m);
n.rotate_left(<u64 as Word>::bit_size() as u32);

fn rotate_right(self, n: u32) -> Self

Shifts the bits to the right by a specified amount, n, wrapping the truncated bits to the beginning of the resulting integer.

Panics

If n > bit_size().

Intrinsics:

  • BMI 2.0: rorx.

Examples

use bitwise::Word;

let n = 0x0123456789ABCDEFu64;
let m = 0xDEF0123456789ABCu64;

assert_eq!(n.rotate_right(12), m);
n.rotate_right(<u64 as Word>::bit_size() as u32);

fn swap_bytes(self) -> Self

Reverses the byte order of the integer.

Examples

use bitwise::Word;

let n = 0x0123456789ABCDEFu64;
let m = 0xEFCDAB8967452301u64;

assert_eq!(n.swap_bytes(), m);

fn from_be(x: Self) -> Self

Convert an integer from big endian to the target's endianness.

On big endian this is a no-op. On little endian the bytes are swapped.

Examples

use bitwise::Word;

let n = 0x0123456789ABCDEFu64;

if cfg!(target_endian = "big") {
    assert_eq!(u64::from_be(n), n)
} else {
    assert_eq!(u64::from_be(n), n.swap_bytes())
}

fn from_le(x: Self) -> Self

Convert an integer from little endian to the target's endianness.

On little endian this is a no-op. On big endian the bytes are swapped.

Examples

use bitwise::Word;

let n = 0x0123456789ABCDEFu64;

if cfg!(target_endian = "little") {
    assert_eq!(u64::from_le(n), n)
} else {
    assert_eq!(u64::from_le(n), n.swap_bytes())
}

fn to_be(self) -> Self

Convert self to big endian from the target's endianness.

On big endian this is a no-op. On little endian the bytes are swapped.

Examples

use bitwise::Word;

let n = 0x0123456789ABCDEFu64;

if cfg!(target_endian = "big") {
    assert_eq!(n.to_be(), n)
} else {
    assert_eq!(n.to_be(), n.swap_bytes())
}

fn to_le(self) -> Self

Convert self to little endian from the target's endianness.

On little endian this is a no-op. On big endian the bytes are swapped.

Examples

use bitwise::Word;

let n = 0x0123456789ABCDEFu64;

if cfg!(target_endian = "little") {
    assert_eq!(n.to_le(), n)
} else {
    assert_eq!(n.to_le(), n.swap_bytes())
}

fn pow(self, exp: u32) -> Self

Raises self to the power of exp, using exponentiation by squaring.

Panics

If the result does not fit in Self.

Examples

use bitwise::Word;

assert_eq!(2i32.pow(4), 16);

fn reverse_bit_groups(self, subword_bits: u32, group_subwords: u32) -> Self

Reverses the bits of self by subword_bits and group_subwords:

  • subword_bits: the bits will be reversed in grous: 1 (single bits), 2 (pair-wise), 4 (nibbles),
  • group_subwords: the subword size is 8 bits: mem::size_of::<u8>(), the bits will be reversed within each subword.

Examples

use bitwise::Word;

let n = 0b0101_1101_1010_0101_u16;

// Single bits:
let s0 = 0b1010_0101_1011_1010u16;
assert_eq!(n.reverse_bit_groups(1, 1), s0);

// Bit pairs:
let s1 = 0b0101_1010_0111_0101u16;
assert_eq!(n.reverse_bit_groups(2, 1), s1);

// Bit nibbles:
let s2 = 0b0101_1010_1101_0101u16;
assert_eq!(n.reverse_bit_groups(4, 1), s2);

// Single bits: group_subwords = 2
let s3 = 0b1011_1010_1010_0101u16;
assert_eq!(n.reverse_bit_groups(1, 2), s3);

// Bit pairs: group_subwords = 2
let s4 = 0b0111_0101_0101_1010u16;
assert_eq!(n.reverse_bit_groups(2, 2), s4);

// Bit nibbles: group_subwords = 2
let s5 = 0b1101_0101_0101_1010u16;
assert_eq!(n.reverse_bit_groups(4, 2), s5);

fn set_bit_to(self, bit: u32, value: bool) -> Self

Sets the bit of self to value.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n  = 0b1001_0011u8;
assert_eq!(n.set_bit_to(6, true), 0b1101_0011u8);
assert_eq!(n.set_bit_to(0, false), 0b1001_0010u8);
assert_eq!(n.set_bit_to(3, true), 0b1001_1011u8);

fn clear_bits_geq(self, bit: u32) -> Self

Clears all bits of self at position >= bit.

Panics

If bit >= bit_size().

Intrinsics:

  • BMI 2.0: bzhi.

Examples

use bitwise::Word;

let n = 0b1111_0010u8;
let s = 0b0001_0010u8;
assert_eq!(n.clear_bits_geq(5), s);

fn is_aligned(self, alignment: u32) -> bool

Is self aligned to alignment bytes.

Returns true if self == 0 or self is a multiple of alignment.

Examples

use bitwise::Word;

assert!(2.is_aligned(1));
assert!(2.is_aligned(2));
assert!(!2.is_aligned(4));
assert!(!2.is_aligned(8));

assert!(3.is_aligned(1));
assert!(!3.is_aligned(2));
assert!(!3.is_aligned(4));
assert!(!3.is_aligned(8));

assert!(4.is_aligned(1));
assert!(4.is_aligned(2));
assert!(4.is_aligned(4));
assert!(!4.is_aligned(8));

fn align_up(self, alignment: u32) -> Self

Align self up to alignment.

Returns n, where n is the least number >= self and is_aligned(n, alignment).

Panics

alignment must be a power of two. which is asserted in debug

Examples

use bitwise::Word;

assert_eq!(2.align_up(1), 2);
assert_eq!(2.align_up(2), 2);
assert_eq!(2.align_up(4), 4);
assert_eq!(2.align_up(8), 8);

assert_eq!(3.align_up(1), 3);
assert_eq!(3.align_up(2), 4);
assert_eq!(3.align_up(4), 4);
assert_eq!(3.align_up(8), 8);

assert_eq!(4.align_up(1), 4);
assert_eq!(4.align_up(2), 4);
assert_eq!(4.align_up(4), 4);
assert_eq!(4.align_up(8), 8);

fn align_down(self, alignment: u32) -> Self

Align self down to alignment.

Returns n, where n is the greatest number <= self and is_aligned(n, alignment).

Panics

alignment must be a power of two.

Examples

use bitwise::Word;

assert_eq!(2.align_down(1), 2);
assert_eq!(2.align_down(2), 2);
assert_eq!(2.align_down(4), 0);
assert_eq!(2.align_down(8), 0);

assert_eq!(3.align_down(1), 3);
assert_eq!(3.align_down(2), 2);
assert_eq!(3.align_down(4), 0);
assert_eq!(3.align_down(8), 0);

assert_eq!(4.align_down(1), 4);
assert_eq!(4.align_down(2), 4);
assert_eq!(4.align_down(4), 4);
assert_eq!(4.align_down(8), 0);

fn outer_perfect_shuffle(self) -> Self

Outer Perfect Shuffle of self.

See also: Hacker's Delight: shuffling bits.

Examples

use bitwise::Word;

let n = 0b0110_0101_1101_1011_1111_1001_0110_0011u32;
//        abcd efgh ijkl mnop ABCD EFGH IJKL MNOP,
let s = 0b0111_1101_0110_0011_1011_0110_1000_1111u32;
//        aAbB cCdD eEfF gGhH iIjJ kKlL mMnN oOpP,

assert_eq!(n.outer_perfect_shuffle(), s);

fn outer_perfect_unshuffle(self) -> Self

Outer Perfect Unshuffle of self.

See also: Hacker's Delight: shuffling bits.

Examples

use bitwise::Word;

let n = 0b0111_1101_0110_0011_1011_0110_1000_1111u32;
//        aAbB cCdD eEfF gGhH iIjJ kKlL mMnN oOpP,
let s = 0b0110_0101_1101_1011_1111_1001_0110_0011u32;
//        abcd efgh ijkl mnop ABCD EFGH IJKL MNOP,

assert_eq!(n.outer_perfect_unshuffle(), s);

fn scatter_bits(self, mask_: Self) -> Self

Scatter the low-ordr bits of self into the positions of the result selected by the mask.

The contiguous low-order bits of self are to be copied to the bits of the destination selected by the mask. in the destination. The bits nothing was copied to are cleared.

Keywords:

Parallel bits deposit, scatter.

Scatter.

Intrinsics:

  • BMI 2.0: pdep.

Examples

use bitwise::Word;

let n  = 0b1011_1110_1001_0011u16;

let m0 = 0b0110_0011_1000_0101u16;
let s0 = 0b0000_0010_0000_0101u16;

let m1 = 0b1110_1011_1110_1111u16;
let s1 = 0b1110_1001_0010_0011u16;

assert_eq!(n.scatter_bits(m0), s0);
assert_eq!(n.scatter_bits(m1), s1);

// The following examples are from Wikipedia:
let w = 0b1101_0101u8;
//        abcd efgh

assert_eq!(w.scatter_bits(0b1111_0000u8), 0b0101_0000u8);
//                                   efgh ____       efgh ____
assert_eq!(w.scatter_bits(0b1111_1100u8), 0b0101_0100u8);
//                                   cdef gh__       cdef gh__
assert_eq!(w.scatter_bits(0b0101_0101u8), 0b0001_0001u8);
//                                   _e_f _g_h       _e_f _g_h
assert_eq!(w.scatter_bits(0b1101_1101u8), 0b0100_1001u8);
//                                   cd_e fg_h       cd_e fg_h
assert_eq!(w.scatter_bits(0b0001_1111u8), 0b0001_0101u8);
//                                   ___d efgh       ___d efgh

fn gather_bits(self, mask_: Self) -> Self

Gather the bits of self selected by the mask into the low-order bits of the result.

The bits from self selected by the mask are copied into the contiguous low order bits of the destination. High-order bits of the destination are cleared.

Keywords:

Gather bits, parallel bits extract.

Intrinsics:

  • BMI 2.0: pext.

Examples

use bitwise::Word;

let n  = 0b1011_1110_1001_0011u16;

let m0 = 0b0110_0011_1000_0101u16;
let s0 = 0b0000_0000_0011_0101u16;

let m1 = 0b1110_1011_1110_1111u16;
let s1 = 0b0001_0111_0100_0011u16;

assert_eq!(n.gather_bits(m0), s0);
assert_eq!(n.gather_bits(m1), s1);

// The following examples are from Wikipedia:
let w = 0b1101_0101u8;
//        abcd efgh

assert_eq!(w.gather_bits(0b1111_0000u8), 0b0000_1101u8);
//                                   abcd ____       ____ abcd
assert_eq!(w.gather_bits(0b1111_1100u8), 0b0011_0101u8);
//                                   abcd ef__       __ab cdef
assert_eq!(w.gather_bits(0b0101_0101u8), 0b0000_1111u8);
//                                   _b_d _f_h       ____ bdfh
assert_eq!(w.gather_bits(0b1101_1101u8), 0b0011_1011u8);
//                                   ab_d ef_h       __ab defh
assert_eq!(w.gather_bits(0b0001_1111u8), 0b0001_0101u8);
//                                   ___d efgh       ___d efgh

fn gather_bit_range(self, first: u32, length: u32) -> Self

Gathers the contiguous low-order bits of self in range [first, first+length] into the low-order bits of the result.

The range increases from low-order to high-order bits, is zero-indexed, and closed.

Keywords:

Extract bit range.

Panics

If first + length >= bit_size().

Intrinsics:

  • BMI 2.0: bextr.

Examples

use bitwise::Word;

let n  = 0b1011_1110_1001_0011u16;
//         abcd efgh ijkl mnop

assert_eq!(n.gather_bit_range(2, 6), 0b0000_0000_0010_0100u16);
//                 [2, 8] => [n, i]    ____ ____ __ij klmn

fn morton_encode_2d(x: [Self; 2]) -> Self

Encode coordinates x into an interleaved Morton index for a Z-Curve.

Layout: xy|xy|xy|xy|... .

Example

use bitwise::Word;

let idx : u64 = 30;
assert_eq!(idx, 0b01_11_10);

let x = idx.morton_decode_2d();

assert!(Word::morton_encode_2d(x) == idx);

assert_eq!(x[0], 0b_110);
assert_eq!(x[1], 0b_011);

fn morton_encode_3d(x: [Self; 3]) -> Self

Encode coordinates x into an interleaved Morton index for a Z-Curve.

Layout: xyz|xyz|xyz|xyz|... .

Example

use bitwise::Word;

let idx : u64 = 30;
assert_eq!(idx, 0b011_110);

let x = idx.morton_decode_3d();

assert!(Word::morton_encode_3d(x) == idx);

assert_eq!(x[0], 0b10);
assert_eq!(x[1], 0b11);
assert_eq!(x[2], 0b01);

fn morton_decode_2d(self) -> [Self; 2]

Decode interleaved Morton index for a Z-Curve into coordinates.

See morton_encode_2d.

fn morton_decode_3d(self) -> [Self; 3]

Decode interleaved Morton index for a Z-Curve into coordinates.

See morton_encode_3d.

Provided Methods

fn bit_size() -> usize

Size of the word in bits.

fn leading_ones(self) -> usize

Returns the number of leading ones in the binary representation of self.

Keywords:

Count leading ones.

Intrinsics:

  • ARMv8: cls.

Examples

use bitwise::Word;

let n = 0b1111_1111_1100_1000u16;

assert_eq!(n.leading_ones(), 10);

fn trailing_ones(self) -> usize

Returns the number of trailing ones in the binary representation of self.

Keywords:

Count trailing ones.

Examples

use bitwise::Word;

let n = 0b0010_0111u16;

assert_eq!(n.trailing_ones(), 3);

fn and_not(self, y: Self) -> Self

Logical and not of self with y.

Intrinsics:

  • BMI 2.0: andn.

Examples

use bitwise::Word;

let n = 0b0100_1101u8;
let m = 0b1110_1010u8;

assert_eq!(n.and_not(m), 0b1010_0010u8);

fn parity(self) -> usize

Returns the number of 1 bits in self mod 2, that is, returns 1 if the number of 1 bits in self is odd, and zero otherwise

Intrinsics:

-gcc/llvm: __builtin_parity(x).

Examples

use bitwise::Word;

let n0 = 0b0000;  // 0 -> even => parity = 0
let n1 = 0b0001;  // 1 -> odd  => partiy = 1
let n2 = 0b0010;  // 1 -> odd  => parity = 1
let n3 = 0b0011;  // 2 -> even => parity = 0

assert_eq!(n0.parity(), 0);
assert_eq!(n1.parity(), 1);
assert_eq!(n2.parity(), 1);
assert_eq!(n3.parity(), 0);

fn next_abs_greater_even(self) -> Self

Returns the next "absolute" even even number x such that |self| < |x| and sign(self) == sign(x).

That is, for positive numbers the next even is greater than self and for negative numbers it is smaller than self (see examples).

Panics

If self overflows.

Examples

use bitwise::Word;

assert_eq!(-3.next_abs_greater_even(), -4);
assert_eq!(-2.next_abs_greater_even(), -4);
assert_eq!(-1.next_abs_greater_even(), -2);
assert_eq!(0.next_abs_greater_even(), 2);
assert_eq!(1.next_abs_greater_even(), 2);
assert_eq!(2.next_abs_greater_even(), 4);
assert_eq!(3.next_abs_greater_even(), 4);

fn prev_abs_smaller_even(self) -> Self

Returns the previous "absolute" even number x such that |x| < |self| and sign(x) == sign(self).

That is, for positive numbers the previous even is smaller than self and for negative numbers it is greater than self (see examples).

Panics

If self overflows. Note that zero is handled as -0 and that the previous even of zero for Unsigned numbers overflows (because its negative).

Examples

use bitwise::Word;

assert_eq!(-3.prev_abs_smaller_even(), -2);
assert_eq!(-2.prev_abs_smaller_even(), 0);
assert_eq!(-1.prev_abs_smaller_even(), 0);
// assert_eq!(0u32.prev_abs_smaller_even(), 2); // overflows
assert_eq!(0.prev_abs_smaller_even(), -2);
assert_eq!(1.prev_abs_smaller_even(), 0);
assert_eq!(2.prev_abs_smaller_even(), 0);
assert_eq!(3.prev_abs_smaller_even(), 2);
assert_eq!(4.prev_abs_smaller_even(), 2);

fn next_abs_greater_equal_even(self) -> Self

Returns the next "absolute" even number x such that |self| <= |x| and sign(self) == sign(x).

That is, for positive numbers the next even is greater or equal than self and for negative numbers it is smaller or equal than self (see examples).

Panics

If self overflows.

Examples

use bitwise::Word;

assert_eq!(-3.next_abs_greater_equal_even(), -4);
assert_eq!(-2.next_abs_greater_equal_even(), -2);
assert_eq!(-1.next_abs_greater_equal_even(), -2);
assert_eq!(0.next_abs_greater_equal_even(), 0);
assert_eq!(1.next_abs_greater_equal_even(), 2);
assert_eq!(2.next_abs_greater_equal_even(), 2);
assert_eq!(3.next_abs_greater_equal_even(), 4);

fn prev_abs_smaller_equal_even(self) -> Self

Returns the previous "absolute" even number x such that |x| <= |self| and sign(x) == sign(self).

That is, for positive numbers the previous even is smaller or equalt than self and for negative numbers it is greater or equalt than self (see examples).

Panics

If self overflows.

Examples

use bitwise::Word;

assert_eq!(-3.prev_abs_smaller_equal_even(), -2);
assert_eq!(-2.prev_abs_smaller_equal_even(), -2);
assert_eq!(-1.prev_abs_smaller_equal_even(), 0);
assert_eq!(0u32.prev_abs_smaller_equal_even(), 0);
assert_eq!(0.prev_abs_smaller_equal_even(), 0);
assert_eq!(1.prev_abs_smaller_equal_even(), 0);
assert_eq!(2.prev_abs_smaller_equal_even(), 2);
assert_eq!(3.prev_abs_smaller_equal_even(), 2);
assert_eq!(4.prev_abs_smaller_equal_even(), 4);

fn next_abs_greater_odd(self) -> Self

Returns the next "absolute" odd number x such that |self| < |x| and sign(self) == sign(x).

That is, for positive numbers the next odd is greater than self and for negative numbers it is smaller than self (see examples).

Panics

If self overflows.

Examples

use bitwise::Word;

assert_eq!(-3.next_abs_greater_odd(), -5);
assert_eq!(-2.next_abs_greater_odd(), -3);
assert_eq!(-1.next_abs_greater_odd(), -3);
assert_eq!(0.next_abs_greater_odd(), 1);
assert_eq!(1.next_abs_greater_odd(), 3);
assert_eq!(2.next_abs_greater_odd(), 3);
assert_eq!(3.next_abs_greater_odd(), 5);

fn prev_abs_smaller_odd(self) -> Self

Returns the previous "absolute" odd number x such that |x| < |self| and sign(x) == sign(self).

That is, for positive numbers the previous odd is smaller than self and for negative numbers it is greater than self (see examples).

Panics

If self overflows. Note that zero is handled as -0 and that the previous odd of zero and one for Unsigned numbers overflows (because its negative).

Examples

use bitwise::Word;

assert_eq!(-4.prev_abs_smaller_odd(), -3);
assert_eq!(-3.prev_abs_smaller_odd(), -1);
assert_eq!(-2.prev_abs_smaller_odd(), -1);
assert_eq!(-1.prev_abs_smaller_odd(), 1);
// assert_eq!(0u32.prev_abs_smaller_odd(), 2); // overflows
//assert_eq!(1u32.prev_abs_smaller_odd(), 2); // overflows
assert_eq!(0.prev_abs_smaller_odd(), -1);
assert_eq!(1.prev_abs_smaller_odd(), -1);
assert_eq!(2.prev_abs_smaller_odd(), 1);
assert_eq!(3.prev_abs_smaller_odd(), 1);
assert_eq!(4.prev_abs_smaller_odd(), 3);

fn next_abs_greater_equal_odd(self) -> Self

Returns the next "absolute" odd odd number x such that |self| <= |x| and sign(self) == sign(x).

That is, for positive numbers the next odd is greater or equal than self and for negative numbers it is smaller or equal than self (see examples).

Panics

If self overflows.

Examples

use bitwise::Word;

assert_eq!(-3.next_abs_greater_equal_odd(), -3);
assert_eq!(-2.next_abs_greater_equal_odd(), -3);
assert_eq!(-1.next_abs_greater_equal_odd(), -1);
assert_eq!(0.next_abs_greater_equal_odd(), 1);
assert_eq!(1.next_abs_greater_equal_odd(), 1);
assert_eq!(2.next_abs_greater_equal_odd(), 3);
assert_eq!(3.next_abs_greater_equal_odd(), 3);

fn prev_abs_smaller_equal_odd(self) -> Self

Returns the previous "absolute" odd number x such that |x| <= |self| and sign(x) == sign(self).

That is, for positive numbers the previous odd is smaller or equalt than self and for negative numbers it is greater or equalt than self (see examples).

Panics

If self overflows. Note that the previous of zero is negative and will overflow for Unsigned Integers.

Examples

use bitwise::Word;

assert_eq!(-3.prev_abs_smaller_equal_odd(), -3);
assert_eq!(-2.prev_abs_smaller_equal_odd(), -1);
assert_eq!(-1.prev_abs_smaller_equal_odd(), -1);
// assert_eq!(0u32.prev_abs_smaller_equal_odd(), -1); // overflows
assert_eq!(0.prev_abs_smaller_equal_odd(), -1);
assert_eq!(1.prev_abs_smaller_equal_odd(), 1);
assert_eq!(2.prev_abs_smaller_equal_odd(), 1);
assert_eq!(3.prev_abs_smaller_equal_odd(), 3);
assert_eq!(4.prev_abs_smaller_equal_odd(), 3);

fn clear(self) -> Self

Clear all bits of self.

Equivalent to zero().

Example

use bitwise::Word;

assert_eq!(0b1010_1010u8.clear(), 0u8);

fn clear_least_significant_one(self) -> Self

Clear least significant 1 bit of self; returns 0 if self is 0.

Intrinsics:

  • BMI 1.0: blsr.

Examples

use bitwise::Word;

let n = 0b0110;
let s = 0b0100;

assert_eq!(n.clear_least_significant_one(), s);

fn set_least_significant_zero(self) -> Self

Set least significant 0 bit of self.

Intrinsics:

  • TBM: blcs.

Examples

use bitwise::Word;

let n = 0b0101;
let s = 0b0111;

assert_eq!(n.set_least_significant_zero(), s);

fn isolate_least_significant_one(self) -> Self

Isolate least significant 1 bit of self and returns it; returns 0 if self is 0.

Intrinsics:

  • BMI 1.0: blsi.
  • TBM: blsic, not.

Examples

use bitwise::Word;

let n = 0b0110;
let s = 0b0010;

assert_eq!(n.isolate_least_significant_one(), s);

fn isolate_least_significant_zero(self) -> Self

Set the least significant zero bit of self to 1 and all of the rest to 0.

Intrinsics:

  • TBM: blcic (or: blci, not).

Examples

use bitwise::Word;

let n = 0b0101;
let s = 0b0010;

assert_eq!(n.isolate_least_significant_zero(), s);

fn clear_trailing_ones(self) -> Self

Clear the trailing 1's in self.

Intrinsics:

  • TBM: blcfill.

Examples

use bitwise::Word;

let n = 0b0110_1111;
let s = 0b0110_0000;

assert_eq!(n.clear_trailing_ones(), s);

fn set_trailing_zeros(self) -> Self

Set all of the trailing 0's in self.

Intrinsics:

  • TBM: blsfill.

Examples

use bitwise::Word;

let n = 0b0110_0000u8;
let s = 0b0111_1111u8;

assert_eq!(n.set_trailing_zeros(), s);

fn mask_trailing_zeros(self) -> Self

Returns a mask with all of the trailing 0's of self set.

Intrinsics:

  • TBM: tzmsk.

Examples

use bitwise::Word;

let n = 0b0110_0000u8;
let s = 0b0001_1111u8;

assert_eq!(n.mask_trailing_zeros(), s);

fn mask_trailing_ones(self) -> Self

Returns a mask with all of the trailing 1's of self set.

Intrinsics:

  • TBM: tlmskc, not.

Examples

use bitwise::Word;

let n = 0b0101_1111u8;
let s = 0b0001_1111u8;

assert_eq!(n.mask_trailing_ones(), s);

fn mask_trailing_zeros_and_least_significant_one(self) -> Self

Returns a mask with all of the trailing 0's of self set and the least significant 1 bit set.

Intrinsics:

  • TBM: blsmsk.

Examples

use bitwise::Word;

let n = 0b0101_0000u8;
let s = 0b0001_1111u8;

assert_eq!(n.mask_trailing_zeros_and_least_significant_one(), s);

fn mask_trailing_ones_and_least_significant_zero(self) -> Self

Returns a mask with all of the trailing 1's of self set and the least significant 0 bit set.

Intrinsics:

  • TBM: blcmsk.

Examples

use bitwise::Word;

let n = 0b0101_1111u8;
let s = 0b0011_1111u8;

assert_eq!(n.mask_trailing_ones_and_least_significant_zero(), s);

fn first_bit_set(self) -> usize

Returns the position of the first bit that is set (starting from the low-order bits).

Returns bit_size() if no bit is found.

Keywords:

Find first bit set, find first one, bit scan forward.

Examples:

use bitwise::Word;

assert_eq!(0b0101_1111u8.first_bit_set(), 0);
assert_eq!(0b0101_1100u8.first_bit_set(), 2);
assert_eq!(0b1000_0000u8.first_bit_set(), 7);
assert_eq!(0b0000_0000u8.first_bit_set(), 8);

fn first_bit_clear(self) -> usize

Returns the position of the first bit that is set (starting from the low-order bits).

Returns bit_size() if no bit is found.

Keywords:

Find first zero.

Examples:

use bitwise::Word;

assert_eq!(0b1111_1111u8.first_bit_clear(), 8);
assert_eq!(0b0111_1111u8.first_bit_clear(), 7);
assert_eq!(0b1010_0011u8.first_bit_clear(), 2);
assert_eq!(0b1000_1010u8.first_bit_clear(), 0);

fn reverse_bits(self) -> Self

Reverses the bits of self.

Intrinsics:

  • ARM: rbit (u32 ARMv7, u64 ARMv8).

Examples

use bitwise::Word;

let n = 0b1011_0010u8;
let s = 0b0100_1101u8;
assert_eq!(n.reverse_bits(), s);

let n1 = 0b1011_0010_1010_1001u16;
let s1 = 0b1001_0101_0100_1101u16;
assert_eq!(n1.reverse_bits(), s1);

fn reverse_bit_pairs(self) -> Self

Reverses the pairs of bits of self.

Examples

use bitwise::Word;

let n = 0b1011_0010u8;
let s = 0b1000_1110u8;
assert_eq!(n.reverse_bit_pairs(), s);

let n1 = 0b1011_0010_1010_1001u16;
let s1 = 0b0110_1010_1000_1110u16;
assert_eq!(n1.reverse_bit_pairs(), s1);

fn reverse_bit_nibbles(self) -> Self

Reverses the nibbles of self.

Examples

use bitwise::Word;

let n = 0b1011_0010u8;
let s = 0b0010_1011u8;
assert_eq!(n.reverse_bit_nibbles(), s);

let n1 = 0b1011_0010_1010_1001u16;
let s1 = 0b1001_1010_0010_1011u16;
assert_eq!(n1.reverse_bit_nibbles(), s1);

fn reverse_byte_groups(self, bytes_per_block: u32, blocks_per_group: u32) -> Self

Reverses the bytes of self.

  • bytes_per_block: number of bytes per block to reverse.
  • blocks_per_group: number of blocks per group of blocks.

Examples

use bitwise::Word;

let n = 0b0101_1101_1010_0101_u16;

// Single bytes:
let s0 = 0b1010_0101_0101_1101u16;
assert_eq!(n.reverse_byte_groups(1, 1), s0);

// Single bytes: group_subwords = 2
let s3 = 0b0101_1101_1010_0101u16;
assert_eq!(n.reverse_byte_groups(1, 2), s3);

fn reverse_bytes(self) -> Self

Reverses the bytes of self (equivalent to swap bytes).

Intrinsics:

  • x86_64: bswap.
  • ARM: rev (v5), revsh (v5), rev16 (v6,v8), rev32(v8).
  • gcc/llvm: __builtin_bswap16/32/64.

Examples

use bitwise::Word;

let n = 0b1011_0010u8;
let s = 0b1011_0010u8;
assert_eq!(n.reverse_bytes(), s);
assert_eq!(n.swap_bytes(), s);

let n1 = 0b1011_0010_1010_1001u16;
let s1 = 0b1010_1001_1011_0010u16;
assert_eq!(n1.reverse_bytes(), s1);
assert_eq!(n1.swap_bytes(), s1);

fn set_bit(self, bit: u32) -> Self

Sets the bit of self.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n  = 0b1011_0010u8;
let s0 = 0b1111_0010u8;
let s1 = 0b1011_0011u8;
let s2 = 0b1011_1010u8;
assert_eq!(n.set_bit(6), s0);
assert_eq!(n.set_bit(0), s1);
assert_eq!(n.set_bit(3), s2);

fn clear_bit(self, bit: u32) -> Self

Clears the bit of self.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n = 0b1011_0010u8;
let s0 = 0b0011_0010u8;
let s1 = 0b1011_0000u8;
let s2 = 0b1001_0010u8;
assert_eq!(n.clear_bit(7), s0);
assert_eq!(n.clear_bit(1), s1);
assert_eq!(n.clear_bit(5), s2);

fn flip_bit(self, bit: u32) -> Self

Flip the bit of self.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n = 0b1011_0010u8;
let s0 = 0b0011_0010u8;
let s1 = 0b1111_0010u8;
let s2 = 0b1001_0010u8;
assert_eq!(n.flip_bit(7), s0);
assert_eq!(n.flip_bit(6), s1);
assert_eq!(n.flip_bit(5), s2);

fn test_bit(self, bit: u32) -> bool

Test the bit of self.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n = 0b1011_0010u8;
assert_eq!(n.test_bit(7), true);
assert_eq!(n.test_bit(6), false);
assert_eq!(n.test_bit(5), true);

fn clear_bits_leq(self, bit: u32) -> Self

Clears all bits of self at position <= bit.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n = 0b1111_0010u8;
let s = 0b1100_0000u8;
assert_eq!(n.clear_bits_leq(5), s);

fn set_bits_geq(self, bit: u32) -> Self

Sets all bits of self at position >= bit.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n = 0b1000_0010u8;
let s = 0b1110_0010u8;
assert_eq!(n.set_bits_geq(5), s);

fn set_bits_leq(self, bit: u32) -> Self

Sets all bits of self at position <= bit.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n = 0b1000_0010u8;
let s = 0b1011_1111u8;
assert_eq!(n.set_bits_leq(5), s);

fn flip_bits_geq(self, bit: u32) -> Self

Flip all bits of self at position >= bit.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n = 0b1001_0010u8;
let s = 0b0111_0010u8;
assert_eq!(n.flip_bits_geq(5), s);

fn flip_bits_leq(self, bit: u32) -> Self

Flip all bits of self at position <= bit.

Panics

If bit >= bit_size().

Examples

use bitwise::Word;

let n = 0b1011_0010u8;
let s = 0b1000_1101u8;
assert_eq!(n.flip_bits_leq(5), s);

fn is_pow2(self) -> bool

Is self a power of 2.

Examples

use bitwise::Word;

assert!(2.is_pow2());
assert!(!3.is_pow2());
assert!(4.is_pow2());
assert!(!5.is_pow2());
assert!(!6.is_pow2());
assert!(!7.is_pow2());
assert!(8.is_pow2());

fn ceil_pow2(self) -> Self

Round self to the next power of 2.

Panics

If the next power of 2 cannot be represented by Self.

Examples

use bitwise::Word;

assert_eq!(2.ceil_pow2(), 2);
assert_eq!(3.ceil_pow2(), 4);
assert_eq!(4.ceil_pow2(), 4);
assert_eq!(5.ceil_pow2(), 8);
assert_eq!(6.ceil_pow2(), 8);
assert_eq!(7.ceil_pow2(), 8);
assert_eq!(8.ceil_pow2(), 8);
assert_eq!(2u32.pow(30).ceil_pow2(), 2u32.pow(30));
assert_eq!((2u32.pow(30) + 1).ceil_pow2(), 2u32.pow(31));
assert_eq!(2u32.pow(31).ceil_pow2(), 2u32.pow(31));
// panics:
// assert_eq!((2u32.pow(31) + 1).ceil_pow2(), 2u32.pow(32));

fn floor_pow2(self) -> Self

Round self to the previous power of 2.

Panics

If self <= 0.

Examples

use bitwise::Word;

assert_eq!(2.floor_pow2(), 2);
assert_eq!(3.floor_pow2(), 2);
assert_eq!(4.floor_pow2(), 4);
assert_eq!(5.floor_pow2(), 4);
assert_eq!(6.floor_pow2(), 4);
assert_eq!(7.floor_pow2(), 4);
assert_eq!(8.floor_pow2(), 8);

fn average_floor(x: Self, y: Self) -> Self

Average without overflow (rounds to the smallest value).

Example

use bitwise::Word;

// The following would overflow:
let a = u64::max_value() / 2;
let b = a + 1;
let result = u64::max_value() / 2;
assert_eq!(<u64 as Word>::average_floor(a, b), result);
assert_eq!(<u64 as Word>::average_floor(b, a), result);

fn average_ceil(x: Self, y: Self) -> Self

Average without overflow (rounds to the largest value).

Example

use bitwise::Word;

// The following would overflow:
let a = u64::max_value() / 2 + 1;
let b = a - 1;
let result = u64::max_value() / 2 + 1;
assert_eq!(<u64 as Word>::average_ceil(a, b), result);
assert_eq!(<u64 as Word>::average_ceil(b, a), result);

fn inner_perfect_shuffle(self) -> Self

Inner Perfect Shuffle of self.

See also: Hacker's Delight: shuffling bits.

Examples

use bitwise::Word;

let n = 0b0110_0101_1101_1011_1111_1001_0110_0011u32;
//        abcd efgh ijkl mnop ABCD EFGH IJKL MNOP,
let s = 0b1011_1110_1001_0011_0111_1001_0100_1111u32;
//        AaBb CcDd EeFf GgHh IiJj KkLl MmNn OoPp

assert_eq!(n.inner_perfect_shuffle(), s);

fn inner_perfect_unshuffle(self) -> Self

Inner Perfect Unshuffle of self.

See also: Hacker's Delight: shuffling bits.

Examples

use bitwise::Word;

let n = 0b1011_1110_1001_0011_0111_1001_0100_1111u32;
//        AaBb CcDd EeFf GgHh IiJj KkLl MmNn OoPp
let s = 0b0110_0101_1101_1011_1111_1001_0110_0011u32;
//        abcd efgh ijkl mnop ABCD EFGH IJKL MNOP,

assert_eq!(n.inner_perfect_unshuffle(), s);

Implementors