//! 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());
    }
}
