Clash Royale CLAN TAG#URR8PPP

Find XOR of two non negative integers without using ^ in swift?

The XOR operation can be extended to non-negative integers. Let K and L be two such integers, and A and B their binary representation. (For the sake of simplicity, if one of them is shorter, let us add some leading zeros, so that A and B are of the same length.)
The bitwise XOR of K and L (denoted as K bitxor L) is defined in the following way: Build a sequence of bits C by taking XOR of bits from A and B at the same position. C is a binary representation of K bitxor L.

For example, for K = 12 and L = 21 we obtain:

A = 01100

B = 10101

C = 11001

and C is a binary representation of K bitxor L = 25.

Also if I add condition like, If I want to find bitwise XOR of all
integers between K and L. For example, K = 5 and L = 8 then,
K bitxor L = 12.

How I can achieve this in simple swift program without using ^?

^

12 ^ 21

2 Answers
2

Use bitwise OR and AND:

let a: UInt = 12
let b: UInt = 21

let c = (a | b) - (a & b)
print(c)


25


Roll your own by converting to binary digits:

let a: UInt = 12
let b: UInt = 21

// Convert to arrays of binary digits
var ba = Array(String(a, radix: 2))
var bb = Array(String(b, radix: 2))

print(ba)
print(bb)


["1", "1", "0", "0"]
["1", "0", "1", "0", "1"]


// Pad shorter array with leading "0"s
if ba.count < bb.count
ba = Array(repeating: "0", count: bb.count - ba.count) + ba
else if bb.count < ba.count
bb = Array(repeating: "0", count: ba.count - bb.count) + bb


print(ba)
print(bb)


["0", "1", "1", "0", "0"]
["1", "0", "1", "0", "1"]


// Perform XOR
let xor = zip(ba, bb).map a, b in a == b ? "0" : "1"
print(xor)


["1", "1", "0", "0", "1"]


// Join digits into a String and convert to UInt
if let c = UInt(xor.joined(), radix: 2)
print(c)



25


I want to find bitwise XOR of all integers between K and L. For
example, K = 5 and L = 8 then, K bitxor L = 12.

To XOR multiple values, just repeatedly XOR each value to the running total:

// Example bitxor of two values
func bitxor(a: UInt, b: UInt) -> UInt b) - (a & b)


// bitxor an array of values
func bitxor(values: [UInt]) -> UInt
return values.reduce (0) result, item in bitxor(a: result, b: item)


// Find XOR of 5...8
print(bitxor(values: Array(UInt(5)...UInt(8))))


12


A faster solution for XOR-ing values in a range

@ViruMax noted in the comments:

Time complexity of this solution is high. For input K = 0 & L = 1000000000, it takes a lot of time.

This is a fair criticism. This can be done much more quickly by exploiting the patterns in the binary numbers and the resulting XORs. This solution is
based on this Q & A. The question presents the fast solution and the accepted answer explains how it works.

Here is the solution in Swift:

func bitXorZeroTo(_ a: UInt) -> UInt
return [a, 1, a + 1, 0][Int(a % 4)]


func bitXorRange(low: UInt, high: UInt) -> UInt
var low = low
var high = high
if low > high
(low, high) = (high, low)

if low == 0
return bitXorZeroTo(high)
else
return bitXorZeroTo(high) ^ bitXorZeroTo(low - 1)




print(bitXorRange(low: 0, high: 1000000000))


1000000000

The time complexity of this solution is O(1).

You can use bitwise XOR ^ like 12 ^ 21

^

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.