auto merge of #19640 : aliblong/rust/power_of_two_reform, r=Gankro

The `is_power_of_two()` method of the `UnsignedInt` trait currently returns `true` for `self == 0`. Zero is not a power of two, assuming an integral exponent `k >= 0`. I've therefore moved this functionality to the new method `is_power_of_two_or_zero()` and reformed `is_power_of_two()` to return false for `self == 0`.

To illustrate the usefulness of the existence of both functions, consider `HashMap`. Its capacity must be zero or a power of two; conversely, it also requires a (non-zero) power of two for key and val alignment.

Also, added a small amount of documentation regarding #18604.

1 files changed, 11 insertions, 16 deletions

diff --git a/src/libcore/num/mod.rs b/src/libcore/num/mod.rs
index b4f867b4bb4..84d1d8e459a 100644
--- a/src/libcore/num/mod.rs
+++ b/src/libcore/num/mod.rs
@@ -673,35 +673,30 @@ signed_int_impl! { int }
 #[unstable = "recently settled as part of numerics reform"]
 pub trait UnsignedInt: Int {
     /// Returns `true` iff `self == 2^k` for some `k`.
+    #[inline]
     fn is_power_of_two(self) -> bool {
-        (self - Int::one()) & self == Int::zero()
+        (self - Int::one()) & self == Int::zero() && !(self == Int::zero())
     }
 
     /// Returns the smallest power of two greater than or equal to `self`.
+    /// Unspecified behavior on overflow.
     #[inline]
     fn next_power_of_two(self) -> Self {
-        let halfbits = size_of::<Self>() * 4;
-        let mut tmp = self - Int::one();
-        let mut shift = 1u;
-        while shift <= halfbits {
-            tmp = tmp | (tmp >> shift);
-            shift = shift << 1u;
-        }
-        tmp + Int::one()
+        let bits = size_of::<Self>() * 8;
+        let one: Self = Int::one();
+        one << ((bits - (self - one).leading_zeros()) % bits)
     }
 
     /// Returns the smallest power of two greater than or equal to `n`. If the
     /// next power of two is greater than the type's maximum value, `None` is
     /// returned, otherwise the power of two is wrapped in `Some`.
     fn checked_next_power_of_two(self) -> Option<Self> {
-        let halfbits = size_of::<Self>() * 4;
-        let mut tmp = self - Int::one();
-        let mut shift = 1u;
-        while shift <= halfbits {
-            tmp = tmp | (tmp >> shift);
-            shift = shift << 1u;
+        let npot = self.next_power_of_two();
+        if npot >= self {
+            Some(npot)
+        } else {
+            None
         }
-        tmp.checked_add(Int::one())
     }
 }