Hello everyone,
I would like to start a pitch about adding a property to stdlib for checking whether an integer is a power of two. Comments are welcome!
Introduction
Checking some mathematical properties of integers (e.g., parity, divisibility, etc.) is widely used in scientific and engineering applications. While Swift's standard library provides a convenient method isMultiple(of:) to test whether an integer is a multiple of another, there are other cases that are not yet supported. A frequently used one is to check if an integer is power of two. This pitch would like to address this problem by adding a computed property isPowerOf2 to the BinaryInteger protocol.
Motivation
It is commonly seen that programmers query if an integer is a power of two. Although the logic is conceptually simple, it would be substantially beneficial to have a standard implementation.
Commonality
There is a decade old question about How to check if a number is a power of 2 on Stack Overflow with ~200K views. There are public demands for such functionality, and it has been or will be officially supported by the libraries of many popular languages, such as C++20, D Programming Language, and .NET Framework.
Below are some uses in apple/swift.
// Example (1) - stdlib/public/core/HashTable.swift
internal struct _HashTable {
internal init(words: UnsafeMutablePointer<Word>, bucketCount: Int) {
_internalInvariant(bucketCount > 0 && bucketCount & (bucketCount - 1) == 0,
"bucketCount must be a power of two")
...
}
}
// Example (2) - stdlib/public/core/Integers.swift
extension BinaryInteger {
internal func _description(radix: Int, uppercase: Bool) -> String {
// Bit shifting can be faster than division when `radix` is a power of two
let isRadixPowerOfTwo = radix.nonzeroBitCount == 1
...
}
}
// Example (3) - stdlib/public/core/Misc.swift
func _isPowerOf2(_ x: UInt) -> Bool {
// implementation
}
func _isPowerOf2(_ x: Int) -> Bool {
// implementation very similar to above
}
// stdlib/public/core/Builtin.swift
internal func _roundUpImpl(_ offset: UInt, toAlignment alignment: Int) -> UInt {
_internalInvariant(_isPowerOf2(alignment))
...
}
Readability
When programmers write code like n > 0 && n & (n - 1) == 0, they often need to leave some comments as well to indicate its underlying functionality, which is not intuitive to many people. As a result, n.isPowerOf2 is much more fluent.
Discoverability
This is very similar to the case of isMultiple. It can be suggested by IDE’s autocompletion. Notably, it works as a companion to isMultiple, and they can improve the discoverability of each other.
Performance
It can be more performant than user code, since the optimal implementation is a bit tricky and thus may not be obvious to some users (e.g., Example (2)).
Abstraction
Some users, especially those not familiar to the relevant type hierarchy, may have their own implementation targeting inappropriate types (e.g., the overloads for both Int and UInt in Example(3) causing duplicate code).
Proposed Solution
It could be a straightforward solution by adding a computed property to the BinaryInteger protocol.
extension BinaryInteger {
@inlinable
public var isPowerOf2: Bool {
return self > 0 && self & (self - 1) == 0
}
}
Source Compatibility
Addictive change only.
Effect on ABI stability
Addictive change only.
Effect on API resilience
Addictive change only.
Alternative Considered
Given that we already have isMultiple(of:) in stdlib, a more generic form isPower(of:) instead of isPowerOf2 would be good for consistency considerations. This was discussed earlier when SE-0225 was being proposed.
In practice, however, querying for power of 2 is much more frequent than that of other numbers, for which there isn’t any known efficient implementation. If we’d go with such alternative, the solution would be something like:
extension BinaryInteger {
@inlinable
public func isPower(of other: Self) -> Bool {
if other == 2 {
// short path
return self > 0 && self & (self - 1) == 0
}
// long path
...
}
}
: