0231. 2的幂 Power of Two

问题描述

所有小于1的整数, 都不是2的次幂, 这样就可以过滤到一半的整数了.

方法1, 暴力法

想法很直接, 2^x 数值的个数很有限, 依次生成它们, 然后跟目标整数作一下比对, 看是否相等.

          1 = 0b1
          2 = 0b10
          4 = 0b100
          8 = 0b1000
         16 = 0b10000
         32 = 0b100000
         64 = 0b1000000
        128 = 0b10000000
        256 = 0b100000000
        512 = 0b1000000000
       1024 = 0b10000000000
       2048 = 0b100000000000
       4096 = 0b1000000000000
       8192 = 0b10000000000000
      16384 = 0b100000000000000
      32768 = 0b1000000000000000
      65536 = 0b10000000000000000
     131072 = 0b100000000000000000
     262144 = 0b1000000000000000000
     524288 = 0b10000000000000000000
    1048576 = 0b100000000000000000000
    2097152 = 0b1000000000000000000000
    4194304 = 0b10000000000000000000000
    8388608 = 0b100000000000000000000000
   16777216 = 0b1000000000000000000000000
   33554432 = 0b10000000000000000000000000
   67108864 = 0b100000000000000000000000000
  134217728 = 0b1000000000000000000000000000
  268435456 = 0b10000000000000000000000000000
  536870912 = 0b100000000000000000000000000000
 1073741824 = 0b1000000000000000000000000000000

这个方法要注意处理好边角问题, 先判断整数是否小于1.

#![allow(unused)]
fn main() {
pub fn is_power_of_two1(n: i32) -> bool {
    if n <= 0 {
        return false;
    }
    if n == 1 {
        return true;
    }

    let mut power = 1;
    while 0 < power && power < n {
        power <<= 1;
        if power == n {
            return true;
        }
    }
    false
}
}

方法2, 统计比特位为1的个数

仔细看方法1的说明, 可以发现, 2^x 的比特位中只能有一个是1, 其它都是0.

这是一个重要的2的次幂的特性, 利用这个特性, 可以很快速地判断整数是否为2的次幂.

#![allow(unused)]
fn main() {
// Count ones
pub fn is_power_of_two2(n: i32) -> bool {
    if n <= 0 {
        return false;
    }
    n.count_ones() == 1
}
}

相关问题