3

I need to find the value (or position) of the most significant bit (MSB) of an integer in Swift.

Eg:

  • Input number: 9
  • Input as binary: 1001
  • MS value as binary: 1000 -> (which is 8 in decimal)
  • MS position as decimal: 3 (because 1<<3 == 1000)

Many processors (Intel, AMD, ARM) have instructions for this. In c, these are exposed. Are these instructions similarly available in Swift through a library function, or would I need to implement some bit twiddling?

The value is more useful in my case.

If a position is returned, then the value can be easily derived by a single shift.

Conversely, computing position from value is not so easy unless a fast Hamming Weight / pop count function is available.

Community
  • 1
  • 1
Benjohn
  • 13,228
  • 9
  • 65
  • 127
  • The value is easier to find with bit manipulation (like the thing you linked minus the magic DeBruijn multiply/lookup) but I don't know enough about Swift to say anything about built-ins other than that I couldn't find one – harold May 08 '17 at 20:48

2 Answers2

4

You can use the flsl() function ("find last set bit, long"):

let x = 9
let p = flsl(x)
print(p) // 4

The result is 4 because flsl() and the related functions number the bits starting at 1, the least significant bit.

On Intel platforms you can use the _bit_scan_reverse intrinsic, in my test in a macOS application this translated to a BSR instruction.

import _Builtin_intrinsics.intel

let x: Int32 = 9
let p = _bit_scan_reverse(x)
print(p) // 3
Martin R
  • 529,903
  • 94
  • 1,240
  • 1,382
  • Excellent, thanks – do you know if this compiles to an assembly instruction on intel / ARM? – Benjohn May 08 '17 at 20:50
  • It's worth command clicking that function name and seeing its sibling methods in the library header. Methods are available for the least significant bit also, and variants for `Int32`, `Int64` and just the machine's native word sized `Int` (although the naming seems irregular). – Benjohn May 08 '17 at 20:58
  • 1
    @Benjohn: It seems that it compiles to a library call. On Intel platforms there is also `_bit_scan_reverse()` (which *is* an intrinsic), you can make it available e.g. with `import simd` . I haven't found an equivalent for ARM yet. – Martin R May 08 '17 at 21:21
  • @Benjohn: Re naming: The `l` suffix is for functions taking a `long`, and that happens to be what `Int` is in Swift (32 or 64 bit). – Martin R May 08 '17 at 21:22
  • Related: http://stackoverflow.com/questions/41353482/are-built-in-intrinsic-functions-available-in-swift-3. For some reason, `__builtin_clz` compiles, but gives a linker error. – Martin R May 08 '17 at 21:26
  • Of slightly obscure interest, I discovered that to _compare_ the most significant bit of two integers, there is an amazingly neat bit twiddle you can do. So, the result of `lfsl(a) < lfsl(b)` is equal to `(a < b) && (a < a^b)`, which basically blew my mind with its elegance – and is by good fortune what I actually need to compute. The algorithm is mentioned on the wikipedia page for the [z-order curve](https://en.wikipedia.org/wiki/Z-order_curve). – Benjohn May 09 '17 at 08:39
4

You can use the the properties leadingZeroBitCount and trailingZeroBitCount to find the Most Significant Bit and Least Significant Bit.

For example,

let i: Int = 95

let lsb = i.trailingZeroBitCount
let msb = Int.bitWidth - 1 - i.leadingZeroBitCount

print("i: \(i) = \(String(i, radix: 2))") // i: 95 = 1011111
print("lsb: \(lsb) = \(String(1 << lsb, radix: 2))") // lsb: 0 = 1
print("msb: \(msb) = \(String(1 << msb, radix: 2))") // msb: 6 = 1000000

If you look at the disassembly(ARM Mac) in LLDB for the Least Significant Bit code, it uses a single instruction, clz, to count the zeroed bits. (ARM Reference)

** 15       let lsb = i.trailingZeroBitCount

    0x100ed947c <+188>:  rbit   x9, x8
    0x100ed9480 <+192>:  clz    x9, x9
    0x100ed9484 <+196>:  mov    x10, x9
    0x100ed9488 <+200>:  str    x10, [sp, #0x2d8]
Adam Comer
  • 492
  • 2
  • 10