检查 Scala 中的数字是否为 2 的幂

1. Introduction

In computer science algorithms, determining whether a given number is a power of two is common. The practical applications include optimizing algorithms, memory management, bitwise operations, etc.

In this tutorial, we’ll examine how to check if a number is a power of two in Scala. Note that only positive numbers are considered powers of two.

2. Divide by Two Approach

We can check if a number is a power of two by repeatedly dividing it by two until it either becomes one or is no longer divisible by two. Let’s look at the implementation of this approach:

def isPowerOfTwoByDivision(num: Long): Boolean = {
  @tailrec
  def isPowerRec(n: Long): Boolean = {
    if (n == 1) true
    else if (n % 2 == 0) isPowerRec(n / 2)
    else false
  }
  num > 0 && isPowerRec(num)
}

In the above example, we use tail recursion to repeatedly divide the number until it reduces to one or becomes an odd number. Utilizing tail recursion rather than head recursion guarantees the prevention of stack overflow issues within the program.

3. LazyList Iteration Approach

Another method to perform the check is by using the iterate() method on LazyList:

def isPowerOfTwoByLazyList(num: Long): Boolean = {
  num > 0 && LazyList.iterate(num)(_ / 2).takeWhile(_ > 1).forall(_ % 2 == 0)
}

This approach involves utilizing the iterate() method to divide the number by two continuously. Subsequently, we use takeWhile() and forall() to verify if all resulting numbers are divisible by two.

4. Counting Ones

When we represent numbers in binary format, the powers of two reveal a unique characteristic. In binary format, the powers of two numbers contain exactly one 1-bit while all other bits are zero. As a result, we can easily check if a number is a power of two by converting it into binary format and counting the number of ones:

def isPowerOfTwoByCountingOnes(num: Long): Boolean = {
  num > 0 && num.toBinaryString.count(_ == '1') == 1
}

We can use the toBinaryString() method from the standard library to convert the number into binary format and count the number of ones. This approach is a very compact way to perform the check.

5. Bitwise AND

In binary, a power of two has only one 1-bit, which is at the most significant position. As a result, the binary representation of the number just before a power of two has all its bits flipped compared to the power of two representations.

For example, the binary representation of 16, a power of two, is 10000. In contrast, the binary representation of 15 is 01111. We can notice that these two binary numbers are flipped versions of each other.

By utilizing this characteristic along with the bitwise AND operation, we can effectively check if a given number is a power of two:

def isPowerOfTwoByBitwiseAnd(num: Long): Boolean = {
  num > 0 && (num & (num - 1)) == 0
}

As each bit is flipped in both numbers, performing a bitwise AND operation results in zero.

6. Testing the Implementations

Now that we have implemented various methods to check if a number is a power of two, it’s crucial to perform thorough testing to verify their accuracy. In this scenario, property-based testing can be utilized to cover all cases. We can use ScalaCheck with ScalaTest to define and test the properties. Let’s write the tests for all the above implementations:

private val powerOfTwoFunctions = Seq(
  ("Division", PowerOfTwo.isPowerOfTwoByDivision),
  ("Counting Ones", PowerOfTwo.isPowerOfTwoByCountingOnes),
  ("Bitwise AND", PowerOfTwo.isPowerOfTwoByBitwiseAnd),
  ("LazyList", PowerOfTwo.isPowerOfTwoByLazyList)
)
powerOfTwoFunctions.foreach { (desc, fn) =>
  it should s"[$desc] return true for a number that is power of 2" in {
    val powersOfTwo: Gen[Long] =
      Gen.choose(0, 62).map(n => Math.pow(2, n).toLong)
    forAll(powersOfTwo) { num =>
      fn(num) shouldBe true
    }
  }
  it should s"[$desc] return false for a number that is NOT a power of 2" in {
    val powersOfTwo: Gen[Long] =
      Gen.choose(0, 62).map(n => Math.pow(2, n).toLong)
    val notPowerOf2 = Gen
      .choose(0L, Long.MaxValue)
      .suchThat(n => !powersOfTwo.sample.contains(n))
    forAll(notPowerOf2) { num =>
      fn(num) shouldBe false
    }
  }
  it should s"[$desc] return false for any negative numbers" in {
    val negativeNumbers = Gen.choose(Long.MinValue, 0L)
    forAll(negativeNumbers) { num =>
      fn(num) shouldBe false
    }
  }
}

In this case, we identified three properties associated with numbers that are powers of two and used the ScalaCheck generators to generate test data based on those properties. We verified these three properties for each of our implementations.

7. Conclusion

In this article, we examined various ways to determine whether a number is a power of two. First, we utilized the conventional division method and subsequently leveraged the binary characteristics of powers of two numbers to perform the check. We then demonstrated a robust approach to validating these implementations through property-based testing, ensuring their accuracy and reliability across different test scenarios.

As always, the sample code used in this tutorial is available over on GitHub.

Persistence

REST

Security