CODEWITHSUNDEEP
swiftalgorithm
Nilanshu Jaiswal
Nilanshu Jaiswal

Reputation: 1693

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

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

Upvotes: 0

Views: 1132

Answers (2)

Nilanshu Jaiswal
Nilanshu Jaiswal

Reputation: 1693

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
}

Upvotes: 0

JeremyP
JeremyP

Reputation: 86671

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.

Upvotes: 3

Related Questions