Home/

...

/

Introduction

Introduction

Real-world problems

A variation of bitwise XOR can be used to implement a “releasing process lock” feature in an operating system.

Releasing process lock

Processes acquire and release locks on shared resources, which must be accessed with mutual exclusion. Whenever a process acquires a lock, the OS writes the corresponding process ID in a log file. Similarly, whenever the process releases the lock, the process ID is written to the log file again. Suppose that several processes acquired locks on a shared resource, but only one of these processes released the lock.

We can use bitwise XOR operations to figure out which process did not release the lock. Each process is assigned a number, according to the order in which it acquired the lock. So, the first process that acquired the lock is given the number 1, the second process that acquired the lock is given the number 2, and so on.

Let’s look at an example of this:

Recall the following two properties of XOR:

  • It returns zero if we take XOR of two same numbers.
  • It returns the same number if we XOR with zero.

So, we can XOR all the process IDs in the input; duplicate numbers will zero out each other and we will be left with a single process ID.

Dry-run templates

The following is the implementation of the solution provided for the Two Single Numbers (medium) problem:

Press + to interact
Python 3.5
def find_single_numbers(nums):
    # get the XOR of the all the numbers
    n1xn2 = 0
    for num in nums:
        n1xn2 ^= num
    # get the rightmost bit that is '1'
    rightmost_set_bit = 1
    while (rightmost_set_bit & n1xn2) == 0:
        rightmost_set_bit = rightmost_set_bit << 1
    num1, num2 = 0, 0
    for num in nums:
        if (num & rightmost_set_bit) != 0:  # the bit is set
            num1 ^= num
        else:  # the bit is not set
            num2 ^= num
    return [num1, num2]
def main():
    print('Single numbers are:' +
          str(find_single_numbers([1, 4, 2, 1, 3, 5, 6, 2, 3, 5])))
    print('Single numbers are:' + str(find_single_numbers([2, 1, 3, 2])))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample input #1

Input: [1, 4, 2, 1, 3, 5, 6, 2, 3, 5]

Since there are three loops in the provided solution, the line number column specifies which loop we’re iterating. The loop iteration column gives the iteration number for each loop.

Loop iteration

Line number

num

n1xn2

rightmost_set_bit

num1

num2

-

3

-

0

-

-

-

1

4-5

1

1

-

-

-

2

4-5

4

5

-

-

-

3

4-5

2

7

-

-

-

4

4-5

1

6

-

-

-

5

4-5

3

5

-

-

-

6

4-5

5

0

-

-

-

7

4-5

6

6

-

-

-

8

4-5

2

4

-

-

-

9

4-5

3

7

-

-

-

10

4-5

5

2

-

-

-

-

8

5

2

0

-

-

1

9-10

5

2

2

-

-

-

11

5

2

2

0

0

1

13-17

1

2

2

0

1

2

13-17

4

2

2

0

5

3

13-17

2

2

2

2

5

4

13-17

1

2

2

2

4

5

13-17

3

2

2

1

4

6

13-17

5

2

2

1

1

7

13-17

6

2

2

7

1

8

13-17

2

2

2

5

1

9

13-17

3

2

2

6

1

10

13-17

5

2

2

6

4

Note: In every iteration of the first loop, we XOR num with n1xn2 of the previous iteration. For example, for iteration 2, line 4-5, in the above table, we XOR num = 4 with n1xn2 = 1 from iteration 1.

Sample input #2

Input: [2, 1, 3, 2]

Loop iteration

Line number

num

n1xn2

rightmost_set_bit

num1

num2

-

3

-

0

-

-

-

1

4-5

2

2

-

-

-

2

4-5

1

3

-

-

-

3

4-5

3

0

-

-

-

4

4-5

2

2

-

-

-

-

8

2

2

0

-

-

1

9-10

2

2

2

-

-

-

11

2

2

2

0

0

1

13-17

2

2

2

2

0

2

13-17

1

2

2

0

1

3

13-17

3

2

2

1

1

4

13-17

4

2

2

3

1

Step-by-step solution construction

The first step in our algorithm is to get the XOR for all numbers in the input array. We’ll store this value in a variable n1xn2. Recall that:

  • XOR of the same numbers returns 0.
4 XOR 4 = 0
  • XOR with zero returns the input number.
4 XOR 0 = 4

We’ll update the value of n1xn2with every XOR operation.

The toBinary() function is only for representing the number in binary format. It does not affect code execution. '{0:04b}' is used to specify the number of bits we want in our binary output. For example, if we want an 8-bit representation, we can change this to {0:08b}

Press + to interact
Python 3.5
def toBinary(n):
  return'{0:04b}'.format(n)
def find_single_numbers(nums):
    print("Input array: ", nums)
    print("")
    # get the XOR of the all the numbers
    n1xn2 = 0
    i = 1
    for num in nums:
        print("Loop iteration: ", i, sep = "")
        i+=1
        print("\tCurrent number: ", num, sep = "")
        print("\tXOR variable n1xn2: ", n1xn2, sep = "")
        temp = n1xn2
        n1xn2 ^= num
        print("\t", num, "(", toBinary(num), ") XOR ", temp, "(", toBinary(temp), ") = ", n1xn2, "(", toBinary(n1xn2), ")\n", sep = "")
def main():
    input = [[1, 4, 2, 1, 3, 5, 6, 2, 3, 5], [2, 1, 3, 2]]
    for i in input:
        print('Single numbers are:', str(find_single_numbers(i)), sep = "")
        print(("-"*100)+"\n")
main()

The next step is to get the right-most bit which is 1. As num1 and num2 are two different numbers, they will have at least one bit that is 1, since XOR of the same number is equal to 0. Hence, for a different bit encountered, it’ll be 1.

Getting this rightmost bit will allow us to locate where we have different bits in the two numbers. We initialize rightmost_set_bit with 1 and take bitwise conjunction (AND) with the calculated XOR, n1xn2. If it’s zero, we left shift rightmost_set_bit by 1. We continue this until the conjunction returns a non-zero number and we’ve found the rightmost bit that’s 1.

Press + to interact
Python 3.5
def toBinary(n):
  return'{0:04b}'.format(n)
def find_single_numbers(nums):
    print("Input array: ", nums)
    print("")
    # get the XOR of the all the numbers
    n1xn2 = 0
    i = 1
    print("Computing XOR of all numbers")
    for num in nums:
        print("\tLoop iteration: ", i, sep = "")
        i+=1
        print("\t\tCurrent number: ", num, sep = "")
        print("\t\tXOR variable n1xn2: ", n1xn2, sep = "")
        temp = n1xn2
        n1xn2 ^= num
        print("\t\t", num, "(", toBinary(num), ") XOR ", temp, "(", toBinary(temp), ") = ", n1xn2, "(", toBinary(n1xn2), ")\n", sep = "")
    # get the rightmost bit that is '1'
    print("Getting the rightmost bit that's 1")
    rightmost_set_bit = 1
    print("\tInitial rightmost set bit: ", rightmost_set_bit, sep = "")
    j = 1
    while (rightmost_set_bit & n1xn2) == 0:
        print("\tLoop iteration: ", j, sep = "")
        j+=1
        temp = rightmost_set_bit & n1xn2
        print("\t\trightmost_set_bit AND n1xn2: ",rightmost_set_bit, "(", toBinary(rightmost_set_bit), ") AND ", n1xn2, "(", toBinary(n1xn2), ") = ", temp, "(", toBinary(temp), ")", sep = "" )
        print("\t\tSince it's 0 ---> left shift the rightmost bit by 1.")
        rightmost_set_bit = rightmost_set_bit << 1
        print("\t\tUpdated rightmost set bit: ", rightmost_set_bit, "(", toBinary(rightmost_set_bit), ")\n", sep = "")
    
    if (rightmost_set_bit & n1xn2) != 0:
        temp = rightmost_set_bit & n1xn2
        print("\trightmost_set_bit AND n1xn2: ",rightmost_set_bit, "(", toBinary(rightmost_set_bit), ") AND ", n1xn2, "(", toBinary(n1xn2), ") = ", temp, "(", toBinary(temp), ")", sep = "" )
        print("\tSince its not 0 ---> we have found the rightmost bit that's 1.")
    print("\tRightmost set bit: ", rightmost_set_bit, "(", toBinary(rightmost_set_bit), ")\n", sep = "")
def main():
    input = [[1, 4, 2, 1, 3, 5, 6, 2, 3, 5], [2, 1, 3, 2]]
    for i in input:
        print('Single numbers are: ', str(find_single_numbers(i)), sep = "")
        print(("-"*100)+"\n")
main()

Lastly, we partition our input array into two groups based on our rightmost_set_bit. One group will consist of all those numbers with that bit set to 0 and the other with the bit set to 1.

We take the XOR of all the numbers in the two groups separately. The calculated XORs will be our required numbers, as all other numbers in each group will cancel each other.

We’ll take bitwise AND of rightmost_set_bit with the numbers in our input array. If the bit is set and the result is not zero, we’ll take the XOR with num1, else, we’ll take it with num2.

  • Group 1: The bit is set.
  • Group 2: The bit is not set.
Press + to interact
Python 3.5
def toBinary(n):
  return'{0:04b}'.format(n)
def find_single_numbers(nums):
    print("Input array: ", nums)
    print("")
    # get the XOR of the all the numbers
    n1xn2 = 0
    i = 1
    print("Computing XOR of all numbers")
    for num in nums:
        print("\tLoop iteration: ", i, sep = "")
        i+=1
        print("\t\tCurrent number: ", num, sep = "")
        print("\t\tXOR variable n1xn2: ", n1xn2, sep = "")
        temp = n1xn2
        n1xn2 ^= num
        print("\t\t", num, "(", toBinary(num), ") XOR ", temp, "(", toBinary(temp), ") = ", n1xn2, "(", toBinary(n1xn2), ")\n", sep = "")
    # get the rightmost bit that is '1'
    print("Getting the rightmost bit that's 1")
    rightmost_set_bit = 1
    print("\tInitial rightmost set bit: ", rightmost_set_bit, sep = "")
    j = 1
    while (rightmost_set_bit & n1xn2) == 0:
        print("\tLoop iteration: ", j, sep = "")
        j+=1
        temp = rightmost_set_bit & n1xn2
        print("\t\trightmost_set_bit AND n1xn2: ",rightmost_set_bit, "(", toBinary(rightmost_set_bit), ") AND ", n1xn2, "(", toBinary(n1xn2), ") = ", temp, "(", toBinary(temp), ")", sep = "" )
        print("\t\tSince it's 0 ---> left shift the rightmost bit by 1.")
        rightmost_set_bit = rightmost_set_bit << 1
        print("\t\tUpdated rightmost set bit: ", rightmost_set_bit, "(", toBinary(rightmost_set_bit), ")\n", sep = "")
    
    if (rightmost_set_bit & n1xn2) != 0:
        temp = rightmost_set_bit & n1xn2
        print("\trightmost_set_bit AND n1xn2: ",rightmost_set_bit, "(", toBinary(rightmost_set_bit), ") AND ", n1xn2, "(", toBinary(n1xn2), ") = ", temp, "(", toBinary(temp), ")", sep = "" )
        print("\tSince its not 0 ---> we have found the rightmost bit that's 1.")
    print("\tRightmost set bit: ", rightmost_set_bit, "(", toBinary(rightmost_set_bit), ")\n", sep = "")
    num1, num2 = 0, 0
    print("Partitioning array elements and computing XOR")
    k = 1
    for num in nums:
        print("\tLoop iteration: ", k, sep = "")
        k+=1
        bitAND = num & rightmost_set_bit
        if (num & rightmost_set_bit) != 0:  # the bit is set
            print("\t\tCurrent number: ", num, "(", toBinary(num), ")", sep = "")
            print("\t\tRightmost set bit: ", rightmost_set_bit, "(", toBinary(rightmost_set_bit), ")", sep = "")
            temp = num & rightmost_set_bit
            print("\t\t", num, "(", toBinary(num), ")", " AND ", rightmost_set_bit, "(", toBinary(rightmost_set_bit), ") = ", temp, "(", toBinary(temp), ") ---> not 0, update num1", sep = "")
            tempnum = num1
            num1 ^= num
            print("\t\tUpdating num1: num1 XOR current number: ", tempnum,"(", toBinary(tempnum), ") XOR ", num, "(", toBinary(num), ") = " , num1, "(", toBinary(num1), ")", sep = "")
        else:  # the bit is not set
            print("\t\tCurrent number: ", num, "(", toBinary(num), ")", sep = "")
            print("\t\tRightmost set bit: ", rightmost_set_bit, "(", toBinary(rightmost_set_bit), ")", sep = "")
            temp = num & rightmost_set_bit
            print("\t\t", num, "(", toBinary(num), ")", " AND ", rightmost_set_bit, "(", toBinary(rightmost_set_bit), ") = ", temp, "(", toBinary(temp), ") ---> update num2", sep = "")
            tempnum = num2
            num2 ^= num
            print("\t\tUpdating num2: num2 XOR current number: ", tempnum,"(", toBinary(tempnum), ") XOR ", num, "(", toBinary(num), ") = " , num2, "(", toBinary(num2), ")", sep = "")
        print("")
    return [num1, num2]
def main():
    input = [[1, 4, 2, 1, 3, 5, 6, 2, 3, 5], [2, 1, 3, 2]]
    for i in input:
        print('Single numbers are: ', str(find_single_numbers(i)), sep = "")
        print(("-"*100)+"\n")
main()