The Beauty of Bit-wise Operation

Bit-wise operator is very useful for increasing performance as well as efficient code.

There are usually 6 bit-wise operations in most of the language:

1. or

2. and

3. xor

4. left shift

5. right shift

6. invert

Among those operators, xor operator is very important for writing efficient code. For example: given a set of numbers where all occur even times except one number, find the odd occurring number.

Solution without using bit-wise operator

//Kotlin Code
fun findOddOccurringNumber(numbers: IntArray): Int {
    val map = mutableMapOf<Int, Int>()

    for (item in numbers) {
        if (map.containsKey(item)) {
            map[item] = map[item]!! + 1
        } else {
            map[item] = 1
        }
    }

    for ((key, value) in map) {
        if (value % 2 != 0) {
            return key
        }
    }

    return 0
}

Solution using xor operator

//Kotlin code
fun findOddOccurringNumber(numbers: IntArray): Int{
    var result = 0
    
    for (item in numbers) {
        result = result xor item
    }

    return result
}

Explanation:

xor output

0 xor 0 = 0

0 xor 1 = 1

1 xor 0 = 1

1 xor 1 = 0

steps :

Sample input 2, 3, 5, 6, 3, 6, 2

0 xor 2 = 2

2 xor 3 = 1

1 xor 5 = 4

4 xor 6 = 2

2 xor 3 = 1

1 xor 6 = 7

7 xor 2 = 5

so result is 5.

Actually even number of xor operation on same number returns zero and odd number of operation return the number. In this way bit-wise operator helps a lot to write efficient code.