Trait malachite_base::num::logic::traits::BitAccess

source · 
pub trait BitAccess {
    fn get_bit(&self, index: u64) -> bool;
    fn set_bit(&mut self, index: u64);
    fn clear_bit(&mut self, index: u64);

    fn assign_bit(&mut self, index: u64, bit: bool) { ... }
    fn flip_bit(&mut self, index: u64) { ... }
}
Expand description

Defines functions that access or modify individual bits in a number.

Required Methods§

Determines whether a number has a true or false bit at index.

Sets the bit at index to true.

Sets the bit at index to false.

Provided Methods§

Sets the bit at index to whichever value bit is.

Worst-case complexity

$T(n) = O(\max(T_S(n), T_C(n)))$,

$M(n) = O(\max(M_S(n), M_C(n)))$

where $T$ is time, $M$ is additional memory, $T_S$ and $M_S$ are the complexities of set_bit, and $T_C$ and $M_C$ are the complexities of clear_bit.

Panics

See panics for set_bit and clear_bit.

Examples found in repository?
src/num/random/striped.rs (line 1584)
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617

    fn next(&mut self) -> Option<T> {
        if self.next_bit == 0 {
            return Some(self.lo_template);
        }
        let mut lo_template = self.lo_template;
        let mut hi_template = self.hi_template;
        let mut first = true;
        let mut previous_forced = true;
        let mut previous_bit = lo_template.get_bit(self.next_bit);
        for next_bit in (0..self.next_bit).rev() {
            let false_possible;
            let true_possible;
            if first {
                false_possible = true;
                true_possible = true;
                lo_template.assign_bit(next_bit, true);
                hi_template.assign_bit(next_bit, true);
                first = false;
            } else {
                lo_template.assign_bit(next_bit, false);
                hi_template.assign_bit(next_bit, false);
                false_possible = ranges_intersect(lo_template, hi_template, self.a, self.b);
                lo_template.assign_bit(next_bit, true);
                hi_template.assign_bit(next_bit, true);
                true_possible = ranges_intersect(lo_template, hi_template, self.a, self.b);
            }
            assert!(false_possible || true_possible);
            let bit = if !false_possible {
                previous_forced = true;
                true
            } else if !true_possible {
                previous_forced = true;
                false
            } else {
                if previous_forced {
                    self.bit_source.end_block();
                    self.bit_source.set_previous_bit(previous_bit);
                    previous_forced = false;
                }
                self.bit_source.next().unwrap()
            };
            if !bit {
                lo_template.assign_bit(next_bit, false);
                hi_template.assign_bit(next_bit, false);
            }
            previous_bit = bit;
        }
        Some(lo_template)
    }

Sets the bit at index to the opposite of its original value.

Worst-case complexity

$T(n) = O(T_G(n) + \max(T_S(n), T_C(n)))$,

$M(n) = O(M_G(n) + \max(M_S(n), M_C(n)))$

where $T$ is time, $M$ is additional memory, $T_G$ and $M_G$ are the complexities of get_bit, $T_S$ and $M_S$ are the complexities of set_bit, and $T_C$ and $M_C$ are the complexities of clear_bit.

Panics

See panics for get_bit, set_bit and clear_bit.

Implementations on Foreign Types§

Determines whether the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are false.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 1.

Setting bits beyond the type’s width is disallowed.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $i \geq W$, where $i$ is index and $W$ is $t::WIDTH.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 0.

Clearing bits beyond the type’s width is allowed; since those bits are already false, clearing them does nothing.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Determines whether the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are false.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 1.

Setting bits beyond the type’s width is disallowed.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $i \geq W$, where $i$ is index and $W$ is $t::WIDTH.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 0.

Clearing bits beyond the type’s width is allowed; since those bits are already false, clearing them does nothing.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Determines whether the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are false.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 1.

Setting bits beyond the type’s width is disallowed.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $i \geq W$, where $i$ is index and $W$ is $t::WIDTH.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 0.

Clearing bits beyond the type’s width is allowed; since those bits are already false, clearing them does nothing.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Determines whether the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are false.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 1.

Setting bits beyond the type’s width is disallowed.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $i \geq W$, where $i$ is index and $W$ is $t::WIDTH.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 0.

Clearing bits beyond the type’s width is allowed; since those bits are already false, clearing them does nothing.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Determines whether the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are false.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 1.

Setting bits beyond the type’s width is disallowed.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $i \geq W$, where $i$ is index and $W$ is $t::WIDTH.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 0.

Clearing bits beyond the type’s width is allowed; since those bits are already false, clearing them does nothing.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Determines whether the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are false.

Let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 1.

Setting bits beyond the type’s width is disallowed.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $i \geq W$, where $i$ is index and $W$ is $t::WIDTH.

Examples

See here.

Sets the $i$th bit of an unsigned primitive integer, or the coefficient of $2^i$ in its binary expansion, to 0.

Clearing bits beyond the type’s width is allowed; since those bits are already false, clearing them does nothing.

Let $$ n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Determines whether the $i$th bit of a signed primitive integer is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are true if the value is negative, and false otherwise.

If $n \geq 0$, let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, i) = (b_i = 1)$.

If $n < 0$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where

  • $W$ is the type’s width
  • for all $i$, $b_i\in \{0, 1\}$, and $b_i = 1$ for $i \geq W$.

Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 1.

Setting bits beyond the type’s width is disallowed if the number is non-negative.

If $n \geq 0$ and $j \neq W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $n < 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n \geq 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 0.

Clearing bits beyond the type’s width is disallowed if the number is negative.

If $n \geq 0$ or $j = W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$ and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}, \end{cases} $$ where $n \geq 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n < 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Determines whether the $i$th bit of a signed primitive integer is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are true if the value is negative, and false otherwise.

If $n \geq 0$, let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, i) = (b_i = 1)$.

If $n < 0$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where

  • $W$ is the type’s width
  • for all $i$, $b_i\in \{0, 1\}$, and $b_i = 1$ for $i \geq W$.

Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 1.

Setting bits beyond the type’s width is disallowed if the number is non-negative.

If $n \geq 0$ and $j \neq W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $n < 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n \geq 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 0.

Clearing bits beyond the type’s width is disallowed if the number is negative.

If $n \geq 0$ or $j = W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$ and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}, \end{cases} $$ where $n \geq 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n < 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Determines whether the $i$th bit of a signed primitive integer is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are true if the value is negative, and false otherwise.

If $n \geq 0$, let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, i) = (b_i = 1)$.

If $n < 0$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where

  • $W$ is the type’s width
  • for all $i$, $b_i\in \{0, 1\}$, and $b_i = 1$ for $i \geq W$.

Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 1.

Setting bits beyond the type’s width is disallowed if the number is non-negative.

If $n \geq 0$ and $j \neq W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $n < 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n \geq 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 0.

Clearing bits beyond the type’s width is disallowed if the number is negative.

If $n \geq 0$ or $j = W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$ and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}, \end{cases} $$ where $n \geq 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n < 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Determines whether the $i$th bit of a signed primitive integer is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are true if the value is negative, and false otherwise.

If $n \geq 0$, let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, i) = (b_i = 1)$.

If $n < 0$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where

  • $W$ is the type’s width
  • for all $i$, $b_i\in \{0, 1\}$, and $b_i = 1$ for $i \geq W$.

Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 1.

Setting bits beyond the type’s width is disallowed if the number is non-negative.

If $n \geq 0$ and $j \neq W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $n < 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n \geq 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 0.

Clearing bits beyond the type’s width is disallowed if the number is negative.

If $n \geq 0$ or $j = W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$ and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}, \end{cases} $$ where $n \geq 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n < 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Determines whether the $i$th bit of a signed primitive integer is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are true if the value is negative, and false otherwise.

If $n \geq 0$, let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, i) = (b_i = 1)$.

If $n < 0$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where

  • $W$ is the type’s width
  • for all $i$, $b_i\in \{0, 1\}$, and $b_i = 1$ for $i \geq W$.

Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 1.

Setting bits beyond the type’s width is disallowed if the number is non-negative.

If $n \geq 0$ and $j \neq W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $n < 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n \geq 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 0.

Clearing bits beyond the type’s width is disallowed if the number is negative.

If $n \geq 0$ or $j = W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$ and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}, \end{cases} $$ where $n \geq 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n < 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Determines whether the $i$th bit of a signed primitive integer is 0 or 1.

false means 0 and true means 1. Getting bits beyond the type’s width is allowed; those bits are true if the value is negative, and false otherwise.

If $n \geq 0$, let $$ n = \sum_{i=0}^\infty 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$; so finitely many of the bits are 1, and the rest are 0. Then $f(n, i) = (b_i = 1)$.

If $n < 0$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where

  • $W$ is the type’s width
  • for all $i$, $b_i\in \{0, 1\}$, and $b_i = 1$ for $i \geq W$.

Then $f(n, j) = (b_j = 1)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 1.

Setting bits beyond the type’s width is disallowed if the number is non-negative.

If $n \geq 0$ and $j \neq W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$, and $W$ is the width of the type. Then $$ n \gets \begin{cases} n + 2^j & \text{if} \quad b_j = 0, \\ n & \text{otherwise}, \end{cases} $$ where $n < 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n \geq 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Sets the $i$th bit of a signed primitive integer to 0.

Clearing bits beyond the type’s width is disallowed if the number is negative.

If $n \geq 0$ or $j = W - 1$, let $$ n = \sum_{i=0}^{W-1} 2^{b_i}; $$ but if $n < 0$ or $j = W - 1$, let $$ 2^W + n = \sum_{i=0}^{W-1} 2^{b_i}, $$ where for all $i$, $b_i\in \{0, 1\}$ and $W$ is the width of the type. Then $$ n \gets \begin{cases} n - 2^j & \text{if} \quad b_j = 1, \\ n & \text{otherwise}, \end{cases} $$ where $n \geq 0$ or $j < W$.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if $n < 0$ and $i \geq W$, where $n$ is self, $i$ is index and $W$ is the width of the type.

Examples

See here.

Implementors§