# Adding isPowerOf2 to BinaryInteger

**URL:** <https://forums.swift.org/t/adding-ispowerof2-to-binaryinteger/24087>\
**Category:** Pitches\
**Created:** [May 3, 2019, 6:03am UTC](https://forums.swift.org/t/adding-ispowerof2-to-binaryinteger/24087 "2019-05-03T06:03:59Z")\
**Posts on this page:** 1\
**Showing post:** 24

<div class="post-metadata">

**Author:** ![dingobye](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dingobye/32/7265_2.png) [@dingobye](https://forums.swift.org/u/dingobye)\
**Post date:** [May 8, 2019, 9:01am UTC](https://forums.swift.org/t/adding-ispowerof2-to-binaryinteger/24087/24 "2019-05-08T09:01:26Z")

</div>

I have done some experiments to compare the performance of different strategies, including `isPowerOf2` (the straight forward solution), `isPowerOf2_ctpop` (the popcount implementation), and `isPower(of:)` (the more general interface). The table below shows the execution time (in sec) for type `Int` under the `-O` optimization level across a range of devices.

| . | iMac (3.8G Core i5) | Macbook Pro (2.9G Core i7) | iPhone X Max | iPhone X | iPhone 6S | iPad Air (A1474) |
| --- | --- | --- | --- | --- | --- | --- |
| isPowerOf2 | 0.083 | 0.098 | 0.121 | 0.148 | 0.194 | 0.305 |
| isPowerOf2\_ctpop | 0.135 | 0.154 | 0.121 | 0.148 | 0.222 | 0.343 |
| isPower(of: 2) | 0.082 | 0.097 | 0.121 | 0.148 | 0.193 | 0.305 |
| isPower(of: 3) | 1.330 | 1.472 | 1.442 | 1.603 | 3.102 | 3.775 |

It can be seen that:

- The popcount implementation can be as efficient as `isPowerOf2` on some latest devices (e.g., iPhone X and iPhone X Max), but overall is less performant.
- In addition, `isPower(of: 2)` (i.e., the slow path of the general interface `isPower(of:)`) is as efficient as `isPowerOf2`.
- Moreover, the complexity of `isPower(of: non2)` is O(log(self) with base non2), and it can be an order of magnitude slower than the other three O(1) scenarios. I think it is acceptable because checking for powers of non-2 bases is much less commonly used, and there isn't any known efficient algorithm.

The results for other built-in integer types have a similar pattern to this one, so they are not given in this table. The code of such experiment is shown below:

```swift
import Foundation
extension BinaryInteger {
    // Proposed solution
    @inlinable public var isPowerOf2: Bool {
        return self > 0 && self & (self - 1) == 0
    }

    // Alternative solution #1
    //@{
    @inlinable public func isPower(of other: Self) -> Bool {
        if other == 2 { return self.isPowerOf2 } // fast path
        return self._isPower(of: other) // slow path
    }
    @usableFromInline internal func _isPower(of other: Self) -> Bool {
       // If self is 1, then it is always true.
       if self == 1 { return true }
       // Now self cannot be 1, so it is false when other is 1.
       if other == 1 { return false }
       // If other is 0, then self must be 0; if other is -1, then self must be -1.
       if (other == 0) || (other < 0 && other + 1 == 0) { return self == other }

       // At this point, we have abs(other) > 1.
       guard self % other == 0 else { return false }
       let bound = self / other
       var x: Self = 1
       while (x > 0 ? x : 0 - x) < (bound > 0 ? bound : 0 - bound) { x *= other }
       return x == bound
    }
    //@}
}

extension FixedWidthInteger {
    // Alternative solution #2
    @inlinable public var isPowerOf2_ctpop: Bool {
        return self > 0 && self.nonzeroBitCount == 1
    }
}

func timing(title: String, op: ()->()) {
    let t1 = CFAbsoluteTimeGetCurrent() // <------ Start timing
    op()
    let t2 = CFAbsoluteTimeGetCurrent() // <------ End timing
    let d = String(format: "%.3f", t2 - t1)
    print("\(title): execution time is \(d) s.")
}

func measure<T: FixedWidthInteger>(_ :T.Type, _ repeating: Int = 100_000_000) {
    timing(title: "\(T.self).isPowerOf2 ", op: {
        var n: T = T(1) << (T.bitWidth - 2)
        for _ in 0..<repeating {
            if n.isPowerOf2 {
                n += 1
            } else {
                n -= 1
            }
        }
        guard n != 0 else { exit(-1) }
    })
    timing(title: "\(T.self).isPowerOf2_ctpop", op: {
        var n: T = T(1) << (T.bitWidth - 2)
        for _ in 0..<repeating {
            if n.isPowerOf2_ctpop {
                n += 1
            } else {
                n -= 1
            }
        }
        guard n != 0 else { exit(-1) }
    })
    timing(title: "\(T.self).isPower(of: 2) ", op: {
        var n: T = T(1) << (T.bitWidth - 2)
        for _ in 0..<repeating {
            if n.isPower(of: 2) {
                n += 1
            } else {
                n -= 1
            }
        }
        guard n != 0 else { exit(-1) }
    })
    timing(title: "\(T.self).isPower(of: 3) ", op: {
        var n: T = T(1) << (T.bitWidth - 2)
        for _ in 0..<repeating {
            if n.isPower(of: 3) {
                n += 1
            } else {
                n -= 1
            }
        }
        guard n != 0 else { exit(-1) }
    })
}

measure(UInt8.self)
measure(UInt16.self)
measure(UInt32.self)
measure(UInt64.self)
measure(Int8.self)
measure(Int16.self)
measure(Int32.self)
measure(Int64.self)

```

---

_[View the full topic](https://forums.swift.org/t/adding-ispowerof2-to-binaryinteger/24087)._