auto merge of #12331 : bjz/rust/count-ones, r=alexcrichton

This is inspired by the [function naming in the Julia standard library](http://docs.julialang.org/en/release-0.2/stdlib/base/#Base.count_ones). It seems like a more self-explanatory name, and is more consistent with the accompanying methods, `leading_zeros` and `trailing_zeros`.

10 files changed, 91 insertions, 41 deletions

diff --git a/src/libextra/enum_set.rs b/src/libextra/enum_set.rs
index a17e807b6ee..d036f2c70d7 100644
--- a/src/libextra/enum_set.rs
+++ b/src/libextra/enum_set.rs
@@ -129,7 +129,7 @@ impl<E:CLike> Iterator<E> for Items<E> {
     }
 
     fn size_hint(&self) -> (uint, Option<uint>) {
-        let exact = self.bits.population_count();
+        let exact = self.bits.count_ones();
         (exact, Some(exact))
     }
 }
diff --git a/src/librustc/middle/trans/adt.rs b/src/librustc/middle/trans/adt.rs
index 15fbb54cd11..2c68914d21f 100644
--- a/src/librustc/middle/trans/adt.rs
+++ b/src/librustc/middle/trans/adt.rs
@@ -432,7 +432,7 @@ fn generic_type_of(cx: &CrateContext, r: &Repr, name: Option<&str>, sizing: bool
                 4 => Type::array(&Type::i32(), align_units),
                 8 if machine::llalign_of_min(cx, Type::i64()) == 8 =>
                                  Type::array(&Type::i64(), align_units),
-                a if a.population_count() == 1 => Type::array(&Type::vector(&Type::i32(), a / 4),
+                a if a.count_ones() == 1 => Type::array(&Type::vector(&Type::i32(), a / 4),
                                                               align_units),
                 _ => fail!("unsupported enum alignment: {:?}", align)
             };
diff --git a/src/libstd/num/i16.rs b/src/libstd/num/i16.rs
index e19e7c6c3b8..cbeff5d4aa2 100644
--- a/src/libstd/num/i16.rs
+++ b/src/libstd/num/i16.rs
@@ -25,15 +25,17 @@ use unstable::intrinsics;
 int_module!(i16, 16)
 
 impl Bitwise for i16 {
-    /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+    /// Returns the number of ones in the binary representation of the number.
     #[inline]
-    fn population_count(&self) -> i16 { unsafe { intrinsics::ctpop16(*self) } }
+    fn count_ones(&self) -> i16 { unsafe { intrinsics::ctpop16(*self) } }
 
-    /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+    /// Returns the number of leading zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn leading_zeros(&self) -> i16 { unsafe { intrinsics::ctlz16(*self) } }
 
-    /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+    /// Returns the number of trailing zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn trailing_zeros(&self) -> i16 { unsafe { intrinsics::cttz16(*self) } }
 }
diff --git a/src/libstd/num/i32.rs b/src/libstd/num/i32.rs
index 372d9f680d7..9afc1a14545 100644
--- a/src/libstd/num/i32.rs
+++ b/src/libstd/num/i32.rs
@@ -25,15 +25,17 @@ use unstable::intrinsics;
 int_module!(i32, 32)
 
 impl Bitwise for i32 {
-    /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+    /// Returns the number of ones in the binary representation of the number.
     #[inline]
-    fn population_count(&self) -> i32 { unsafe { intrinsics::ctpop32(*self) } }
+    fn count_ones(&self) -> i32 { unsafe { intrinsics::ctpop32(*self) } }
 
-    /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+    /// Returns the number of leading zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn leading_zeros(&self) -> i32 { unsafe { intrinsics::ctlz32(*self) } }
 
-    /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+    /// Returns the number of trailing zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn trailing_zeros(&self) -> i32 { unsafe { intrinsics::cttz32(*self) } }
 }
diff --git a/src/libstd/num/i64.rs b/src/libstd/num/i64.rs
index 3af082210b9..f1e9f5a4fdc 100644
--- a/src/libstd/num/i64.rs
+++ b/src/libstd/num/i64.rs
@@ -27,15 +27,16 @@ use unstable::intrinsics;
 int_module!(i64, 64)
 
 impl Bitwise for i64 {
-    /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+    /// Returns the number of ones in the binary representation of the number.
     #[inline]
-    fn population_count(&self) -> i64 { unsafe { intrinsics::ctpop64(*self) } }
+    fn count_ones(&self) -> i64 { unsafe { intrinsics::ctpop64(*self) } }
 
-    /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+    /// Returns the number of leading zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn leading_zeros(&self) -> i64 { unsafe { intrinsics::ctlz64(*self) } }
 
-    /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+    /// Counts the number of trailing zeros.
     #[inline]
     fn trailing_zeros(&self) -> i64 { unsafe { intrinsics::cttz64(*self) } }
 }
diff --git a/src/libstd/num/i8.rs b/src/libstd/num/i8.rs
index 66162ce3502..e0e549b731a 100644
--- a/src/libstd/num/i8.rs
+++ b/src/libstd/num/i8.rs
@@ -25,15 +25,17 @@ use unstable::intrinsics;
 int_module!(i8, 8)
 
 impl Bitwise for i8 {
-    /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+    /// Returns the number of ones in the binary representation of the number.
     #[inline]
-    fn population_count(&self) -> i8 { unsafe { intrinsics::ctpop8(*self) } }
+    fn count_ones(&self) -> i8 { unsafe { intrinsics::ctpop8(*self) } }
 
-    /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+    /// Returns the number of leading zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn leading_zeros(&self) -> i8 { unsafe { intrinsics::ctlz8(*self) } }
 
-    /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+    /// Returns the number of trailing zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn trailing_zeros(&self) -> i8 { unsafe { intrinsics::cttz8(*self) } }
 }
diff --git a/src/libstd/num/int.rs b/src/libstd/num/int.rs
index f336afe12f4..d525639045e 100644
--- a/src/libstd/num/int.rs
+++ b/src/libstd/num/int.rs
@@ -27,30 +27,34 @@ use unstable::intrinsics;
 
 #[cfg(target_word_size = "32")]
 impl Bitwise for int {
-    /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+    /// Returns the number of ones in the binary representation of the number.
     #[inline]
-    fn population_count(&self) -> int { (*self as i32).population_count() as int }
+    fn count_ones(&self) -> int { (*self as i32).count_ones() as int }
 
-    /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+    /// Returns the number of leading zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn leading_zeros(&self) -> int { (*self as i32).leading_zeros() as int }
 
-    /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+    /// Returns the number of trailing zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn trailing_zeros(&self) -> int { (*self as i32).trailing_zeros() as int }
 }
 
 #[cfg(target_word_size = "64")]
 impl Bitwise for int {
-    /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+    /// Returns the number of ones in the binary representation of the number.
     #[inline]
-    fn population_count(&self) -> int { (*self as i64).population_count() as int }
+    fn count_ones(&self) -> int { (*self as i64).count_ones() as int }
 
-    /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+    /// Returns the number of leading zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn leading_zeros(&self) -> int { (*self as i64).leading_zeros() as int }
 
-    /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+    /// Returns the number of trailing zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn trailing_zeros(&self) -> int { (*self as i64).trailing_zeros() as int }
 }
diff --git a/src/libstd/num/int_macros.rs b/src/libstd/num/int_macros.rs
index fe3c18d1c4f..3ecc6f32017 100644
--- a/src/libstd/num/int_macros.rs
+++ b/src/libstd/num/int_macros.rs
@@ -614,8 +614,17 @@ mod tests {
     }
 
     #[test]
-    fn test_bitcount() {
-        assert_eq!((0b010101 as $T).population_count(), 3);
+    fn test_count_ones() {
+        assert_eq!((0b0101100 as $T).count_ones(), 3);
+        assert_eq!((0b0100001 as $T).count_ones(), 2);
+        assert_eq!((0b1111001 as $T).count_ones(), 5);
+    }
+
+    #[test]
+    fn test_count_zeros() {
+        assert_eq!((0b0101100 as $T).count_zeros(), BITS as $T - 3);
+        assert_eq!((0b0100001 as $T).count_zeros(), BITS as $T - 2);
+        assert_eq!((0b1111001 as $T).count_zeros(), BITS as $T - 5);
     }
 
     #[test]
diff --git a/src/libstd/num/mod.rs b/src/libstd/num/mod.rs
index 493069139ef..33690a5fddb 100644
--- a/src/libstd/num/mod.rs
+++ b/src/libstd/num/mod.rs
@@ -375,18 +375,35 @@ pub trait Bitwise: Bounded
                  + BitXor<Self,Self>
                  + Shl<Self,Self>
                  + Shr<Self,Self> {
-    /// Returns the number of bits set in the number.
+    /// Returns the number of ones in the binary representation of the number.
     ///
     /// # Example
     ///
     /// ```rust
     /// use std::num::Bitwise;
     ///
-    /// let n = 0b0101000u16;
-    /// assert_eq!(n.population_count(), 2);
+    /// let n = 0b01001100u8;
+    /// assert_eq!(n.count_ones(), 3);
     /// ```
-    fn population_count(&self) -> Self;
-    /// Returns the number of leading zeros in the number.
+    fn count_ones(&self) -> Self;
+
+    /// Returns the number of zeros in the binary representation of the number.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use std::num::Bitwise;
+    ///
+    /// let n = 0b01001100u8;
+    /// assert_eq!(n.count_zeros(), 5);
+    /// ```
+    #[inline]
+    fn count_zeros(&self) -> Self {
+        (!*self).count_ones()
+    }
+
+    /// Returns the number of leading zeros in the in the binary representation
+    /// of the number.
     ///
     /// # Example
     ///
@@ -397,7 +414,9 @@ pub trait Bitwise: Bounded
     /// assert_eq!(n.leading_zeros(), 10);
     /// ```
     fn leading_zeros(&self) -> Self;
-    /// Returns the number of trailing zeros in the number.
+
+    /// Returns the number of trailing zeros in the in the binary representation
+    /// of the number.
     ///
     /// # Example
     ///
diff --git a/src/libstd/num/uint_macros.rs b/src/libstd/num/uint_macros.rs
index bbf1c497c2b..4fc30b43895 100644
--- a/src/libstd/num/uint_macros.rs
+++ b/src/libstd/num/uint_macros.rs
@@ -266,19 +266,21 @@ impl ToStrRadix for $T {
 impl Primitive for $T {}
 
 impl Bitwise for $T {
-    /// Counts the number of bits set. Wraps LLVM's `ctpop` intrinsic.
+    /// Returns the number of ones in the binary representation of the number.
     #[inline]
-    fn population_count(&self) -> $T {
-        (*self as $T_SIGNED).population_count() as $T
+    fn count_ones(&self) -> $T {
+        (*self as $T_SIGNED).count_ones() as $T
     }
 
-    /// Counts the number of leading zeros. Wraps LLVM's `ctlz` intrinsic.
+    /// Returns the number of leading zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn leading_zeros(&self) -> $T {
         (*self as $T_SIGNED).leading_zeros() as $T
     }
 
-    /// Counts the number of trailing zeros. Wraps LLVM's `cttz` intrinsic.
+    /// Returns the number of trailing zeros in the in the binary representation
+    /// of the number.
     #[inline]
     fn trailing_zeros(&self) -> $T {
         (*self as $T_SIGNED).trailing_zeros() as $T
@@ -375,8 +377,17 @@ mod tests {
     }
 
     #[test]
-    fn test_bitcount() {
-        assert_eq!((0b010101 as $T).population_count(), 3);
+    fn test_count_ones() {
+        assert_eq!((0b0101100 as $T).count_ones(), 3);
+        assert_eq!((0b0100001 as $T).count_ones(), 2);
+        assert_eq!((0b1111001 as $T).count_ones(), 5);
+    }
+
+    #[test]
+    fn test_count_zeros() {
+        assert_eq!((0b0101100 as $T).count_zeros(), BITS as $T - 3);
+        assert_eq!((0b0100001 as $T).count_zeros(), BITS as $T - 2);
+        assert_eq!((0b1111001 as $T).count_zeros(), BITS as $T - 5);
     }
 
     #[test]