How to get the binary inverse of a number in Swift?

Question

If we have a given number, say 9 (binary representation is 1001). How can we most efficiently get it's inverse 6 (binary representation is 0110)? i.e replacing 0 with 1 and 1 with 0.

I have written a code of order O(1) complexity? But can there be a better way? Does Swift provide an elegant way of handling this?

Note negate function ~9 results in -10. This is not what I am seeking.

func inverse(of givenNumber: Int) -> Int                             // eg. 9
{
    let binaryRepresentation = String(givenNumber, radix: 2)         // "1001"
    let binaryRepresentationLength = binaryRepresentation.count      // 4
    let maxValueInLength = (1 << binaryRepresentationLength) - 1     // 15, i.e., 1111
    let answer = givenNumber ^ maxValueInLength                      // 6, i.e., 0110
    return answer
}

Edit 1: givenNumber > 0

You can [find the highest set bit](https://stackoverflow.com/questions/53161/find-the-highest-order-bit-in-c) with bit-shifting, too. By the way, your "inverse" is not symmetrical: The inverse of 9 (1001) is 6, but the inverse of 6 (110) would be 1, which I find a bit counterintuitive. And what is the inverse of 0? — M Oehm, Oct 28 '19 at 09:26
@MOehm Bit shifting algorithm is of order O(logN). So the complexity will not become better. Yes, the inverse of 6 would be 1. This is the demand of the question. Symmetry is not the requirement here. Inverse of 0 will be 1. — Nilanshu Jaiswal, Oct 28 '19 at 09:37
@MOehm, why would you need to bit shift for that? `Int.bitWidth - givenNumber.leadingZeroBitCount` will give you the answer right away. (or for general type: `type(of: givenNumber).bitWidth - givenNumber.leadingZeroBitCount`). — user28434'mstep, Oct 28 '19 at 09:41
Will this page help you out? https://docs.swift.org/swift-book/LanguageGuide/AdvancedOperators.html — Rickard Elimää, Oct 28 '19 at 09:44
That's the formal complexity, but I suspect that it will be faster than creating a temporary string object. A binary search will give you O(log(W)), where W is the type's bit width. I didn't know about Swift's `leadingZeroBitCount`, which seems to be what you want. — M Oehm, Oct 28 '19 at 09:54

JeremyP · Accepted Answer · 2019-10-28T10:35:06.113

3

For positive numbers you can use the following:

func intInverse<T: FixedWidthInteger>(of givenNumber: T) -> T                             
{
    assert(!T.isSigned || givenNumber & (T(1) << (givenNumber.bitWidth - 1)) == 0)

    let binaryRepresentationLength = givenNumber.bitWidth - givenNumber.leadingZeroBitCount
    let maxValueInLength = givenNumber.leadingZeroBitCount > 0 ? (~(~T(0) << binaryRepresentationLength)) : ~0
    let answer = givenNumber ^ maxValueInLength 
    return answer
}

Which is identical to your algorithm but doesn't require stringifying the number. It doesn't work for negative numbers, but then neither does your algorithm because your algorithm sticks a - on the front of the number.

Probably the easiest way to extend this to cover negative numbers is to invert all the bits to get the binaryRepresentationLength

EDIT

I changed the way the exclusive or mask is created because the old one crashed for unsigned values with the top bit set and for signed values with the second highest bit set.

edited Oct 28 '19 at 10:35

answered Oct 28 '19 at 09:42

JeremyP

84,577
15
123
161

`For positive numbers` — you can just use `UInt` then. Or you can stick something like ```guard givenNumber > 0 else { return -intInverse(of: -givenNumber) }``` – user28434'mstep Oct 28 '19 at 09:43
@user28434 That depends on context. If you have an `Int` you want to convert, it needs to be for `Int`. Anyway, the above works for any `FixedWidthInteger` so I'll change it. – JeremyP Oct 28 '19 at 09:53
@JeremyP, but if function doesn't works only for 50% of used type, but works for 100% of other type, maybe you need to change type of the function, and make function user convert input/output as they like. – user28434'mstep Oct 28 '19 at 09:56
@user28434 The thing is, I don't know what the "inverse" of a negative number should be. Using my suggestion of inverting the bits, the inverse of -9 is -8, not -6. This is probably an artefact of 2's complement. – JeremyP Oct 28 '19 at 10:04
@user28434 Ha ha, I've just realised it doesn't work 100% for unsigned types either because if the top bit is set, the shift overflows. – JeremyP Oct 28 '19 at 10:09
@JeremyP, my last comment was about sticking to `unsigned` types. In this case declaring that function works only for `unsigned` and making users to convert their data to unsigned is like declaring function to accept only `non-optional` when it can only work with non-optionals. Opposed to your current solution, which is like declaring function input as `T?` but then crashing whole app if input was `nil`. – user28434'mstep Oct 28 '19 at 10:10
@user28434 Can't do that, because, if there is one `FixedWidthInteger` type you want a function to work with, it is `Int`. It would be better to define the function for both positive and negative values (and fix the shift overflow). – JeremyP Oct 28 '19 at 10:13
Still think, you should drop `assert` and limit `T` to `FixedWidthInteger & UnsignedInteger`. – user28434'mstep Oct 30 '19 at 12:19

score 0 · Answer 2 · answered Nov 18 '19 at 09:33

0

The code becomes much simpler using the property binade of a floating-point value.

func inverse(of givenNumber: Int) -> Int                                 // eg. 9
{
    let maxValueInLength = Int((Double(givenNumber).binade * 2) - 1)     // 15, i.e., 1111
    let answer = givenNumber ^ maxValueInLength                          // 6, i.e., 0110
    return answer
}

answered Nov 18 '19 at 09:33

Nilanshu Jaiswal

1,583
3
23
34

This will work up to a point but since the significant does not have 64 bits of precision, it will fail with very large integers e.g. `print(inverse(of: (1 << 53)))` gives the wrong answer. – JeremyP Nov 19 '19 at 08:35

How to get the binary inverse of a number in Swift?

2 Answers2