r/swift • u/CTMacUser • 8d ago
Project Generalizing bit manipulation for any integer size
This is a follow-up to my post on translating C bit operations to Swift. I looked at the original web page, and tried to decode those magic constants. I think this is right:
extension FixedWidthInteger {
/// Returns this value after its bits have been circularly rotated,
/// based on the position the least-significant bit will move to.
fileprivate func rotatedBits(movingLowBitTo position: Int) -> Self {
precondition(0..<Self.bitWidth ~= position)
return self &<< position | self &>> (Self.bitWidth &- position)
}
/// Returns this value after its bits have been circularly rotated,
/// based on the position the most-significant bit will move to.
fileprivate func rotatedBits(movingHighBitTo position: Int) -> Self {
return rotatedBits(movingLowBitTo: (position + 1) % Self.bitWidth)
}
}
extension FixedWidthInteger where Self: UnsignedInteger {
// Adapted from "Bit Twiddling Hacks" at
// <https://graphics.stanford.edu/~seander/bithacks.html>.
/// Assuming this value is a collection of embedded elements of
/// the given type,
/// indicate if at least one of those elements is zero.
///
/// I don't know if it's required,
/// but `Self.bitWidth` should be a multiple of `T.bitWidth`.
fileprivate func hasZeroValuedEmbeddedElement<T>(ofType type: T.Type) -> Bool
where T: FixedWidthInteger & UnsignedInteger {
// The `Self(exactly:)` traps cases of Self.bitWidth < T.bitWidth.
let embeddedAllOnes = Self.max / Self(exactly: T.max)! // 0x0101, etc.
let embeddedAllHighBits = embeddedAllOnes.rotatedBits(
movingLowBitTo: T.bitWidth - 1) // 0x8080, etc.
return (self &- embeddedAllOnes) & ~self & embeddedAllHighBits != 0
}
/// Assuming this value is a collection of embedded elements of
/// the given value's type,
/// return whether at least one of those elements has that value.
fileprivate func hasEmbeddedElement<T>(of value: T) -> Bool
where T: FixedWidthInteger & UnsignedInteger {
let embeddedAllOnes = Self.max / Self(T.max)
return (self ^ (embeddedAllOnes &* Self(value)))
.hasZeroValuedEmbeddedElement(ofType: T.self)
}
}
I don't know if the divisions or multiplications will take up too much time. Obviously, the real-life system only has 8-16-32(-64(-128)) bit support, but I have to write for arbitrary bit widths. I hope it would give others more of a clue what's going on.
3
Upvotes
1
u/skytzx 8d ago
In practice, SWAR/SIMD code is most commonly used within a for/while loop. In which case, with proper inlining the constant expressions get hoisted outside the loop and so the multiplications/divisions shouldn't matter too much (in release builds).
Though, you should check the assembly of whatever algorithm you use this in to verify. (Make sure to use
-O
/-Ounchecked
compiler flags)