Trait malachite_base::num::logic::traits::BitScan

source · [−]
pub trait BitScan {
    fn index_of_next_false_bit(self, start: u64) -> Option<u64>;
    fn index_of_next_true_bit(self, start: u64) -> Option<u64>;
}
Expand description

Defines functions that search for the next true or false bit in a number, starting at a specified index and searching in the more-significant direction.

Required Methods

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

Implementations on Foreign Types

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

Since the number is unsigned and therefore has an implicit prefix of infinitely-many zeros, this function always returns a value.

Starting beyond the type’s width is allowed; the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, the result is None since there are no true bits past that point.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

Since the number is unsigned and therefore has an implicit prefix of infinitely-many zeros, this function always returns a value.

Starting beyond the type’s width is allowed; the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, the result is None since there are no true bits past that point.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

Since the number is unsigned and therefore has an implicit prefix of infinitely-many zeros, this function always returns a value.

Starting beyond the type’s width is allowed; the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, the result is None since there are no true bits past that point.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

Since the number is unsigned and therefore has an implicit prefix of infinitely-many zeros, this function always returns a value.

Starting beyond the type’s width is allowed; the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, the result is None since there are no true bits past that point.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

Since the number is unsigned and therefore has an implicit prefix of infinitely-many zeros, this function always returns a value.

Starting beyond the type’s width is allowed; the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, the result is None since there are no true bits past that point.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

Since the number is unsigned and therefore has an implicit prefix of infinitely-many zeros, this function always returns a value.

Starting beyond the type’s width is allowed; the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, the result is None since there are no true bits past that point.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is negative. If it is, then the result is None since there are no false bits past that point. If the number is non-negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is non-negative. If it is, then the result is None since there are no true bits past that point. If the number is negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is negative. If it is, then the result is None since there are no false bits past that point. If the number is non-negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is non-negative. If it is, then the result is None since there are no true bits past that point. If the number is negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is negative. If it is, then the result is None since there are no false bits past that point. If the number is non-negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is non-negative. If it is, then the result is None since there are no true bits past that point. If the number is negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is negative. If it is, then the result is None since there are no false bits past that point. If the number is non-negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is non-negative. If it is, then the result is None since there are no true bits past that point. If the number is negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is negative. If it is, then the result is None since there are no false bits past that point. If the number is non-negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is non-negative. If it is, then the result is None since there are no true bits past that point. If the number is negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a false bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is negative. If it is, then the result is None since there are no false bits past that point. If the number is non-negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Given a number and a starting index, searches the number for the smallest index of a true bit that is greater than or equal to the starting index.

If the starting index is greater than or equal to the type’s width, then the result depends on whether the number is non-negative. If it is, then the result is None since there are no true bits past that point. If the number is negative, then the result is the starting index.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Implementors