1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//! Power-of-two check for [`U256`].
use super::U256;
impl U256 {
/// Returns `true` if `self` is a power of two.
///
/// Uses the Stanford bit trick `v != 0 && (v & (v - 1)) == 0`. A power of
/// two has exactly one bit set; subtracting 1 clears that bit and sets all
/// lower bits, so the AND produces zero.
///
/// # Examples
///
/// ```
/// use cnfy_uint::u256::U256;
///
/// assert!(U256::ONE.is_power_of_two());
/// assert!(U256::from_be_limbs([0, 0, 0, 256]).is_power_of_two());
/// assert!(!U256::ZERO.is_power_of_two());
/// assert!(!U256::from_be_limbs([0, 0, 0, 3]).is_power_of_two());
/// ```
#[inline]
pub const fn is_power_of_two(&self) -> bool {
let (minus_one, _) = self.overflowing_sub(&U256::ONE);
let and0 = self.0[0] & minus_one.0[0];
let and1 = self.0[1] & minus_one.0[1];
let and2 = self.0[2] & minus_one.0[2];
let and3 = self.0[3] & minus_one.0[3];
!self.is_zero() && (and0 | and1 | and2 | and3) == 0
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
/// Zero is not a power of two.
#[test]
fn zero() {
assert!(!U256::ZERO.is_power_of_two());
}
/// One (2^0) is a power of two.
#[test]
fn one() {
assert!(U256::ONE.is_power_of_two());
}
/// Small powers of two.
#[test]
fn small_powers() {
for shift in 0..64 {
let val = U256::from_be_limbs([0, 0, 0, 1u64 << shift]);
assert!(val.is_power_of_two(), "2^{shift} should be power of two");
}
}
/// Powers of two across all limbs.
#[test]
fn all_limbs() {
assert!(U256::from_be_limbs([1, 0, 0, 0]).is_power_of_two());
assert!(U256::from_be_limbs([0, 1, 0, 0]).is_power_of_two());
assert!(U256::from_be_limbs([0, 0, 1, 0]).is_power_of_two());
assert!(U256::from_be_limbs([0, 0, 0, 1]).is_power_of_two());
}
/// Non-powers return false.
#[test]
fn non_powers() {
assert!(!U256::from_be_limbs([0, 0, 0, 3]).is_power_of_two());
assert!(!U256::from_be_limbs([0, 0, 0, 6]).is_power_of_two());
assert!(!U256::from_be_limbs([1, 0, 0, 1]).is_power_of_two());
assert!(!U256::MAX.is_power_of_two());
}
/// 2^255 (highest single-bit value in U256).
#[test]
fn two_pow_255() {
let val = U256::from_be_limbs([1u64 << 63, 0, 0, 0]);
assert!(val.is_power_of_two());
}
}