Kotlin — Bits & More …

I recently experienced a coding problem that involved working at the bit level to provide the best solution. As it turns out, working through the solution(s) brings to light some interesting examples for learning about features of lists, the Math class, function extensions, and bitwise operations supported by Kotlin.

Coding Challenge

The challenge is to swap all adjacent bits for a given number to produce a new value. The best solution was to solve efficiently and with as few lines of source code as possible. For example, for the 8-bits [ 0100 0101 ] this would result in [1000 1010].

I won’t claim to be the mathematician, computer scientist, hacker, etc. that came up with the most efficient way to solve the problem, so credit is given to those folks in the references.

For this blog entry, the focus is to learn about using available Kotlin features and iterating over various implementations to discover an efficient solution. Along the way, some interesting Kotlin features are used to solve the coding challenge.

Begin Solving

I know, this is a bit of a geeky problem (no pun intended), and may not be something most developers work on day-to-day. However, knowing something about bit manipulation can be important to understand when programming in domains such as: graphics, gaming, security, and device drivers.

Here’s an example of the problem and desired outcome using numbers represented with four bits.

The value 5 represented by 4 bits is 0 1 0 1. The bit setting 0 1 0 1 with each set of bits swapped, yields the value 10 represented in binary with 1 0 1 0.

Working left to right, the bits are swapped for each pair. The original value of 5 now becomes 10 when the bits are swapped in this manner.

How is the value 5 obtained from the bits set as [0 1 0 1]?

Each bit position has an associated value. Working right to left from what is called the least significant bit to the most significant bit, the first and third bits are set, so the values 1 and 4 are summed to become the value 5.

If 1111 then the value would be 15. That is why when 4-bits are used, the minimum value is 0 and the maximum value is 15 or (2⁴) — 1.

When thinking about this problem as a developer who may have never worked with binary data, or doesn’t recall working with bitwise operators, an approach may be to represent the bit set in a Kotlin list or array. This approach would allow the developer to set and get values through sequenced indexes.

Going with this approach initially, a design may represent the following.

1. Create a list of bit settings to represent a number.
2. Construct a list that will hold the swapped bits.
3. Loop over the original bits and swap the bits (placing results in the new list) two-by-two until reaching the end of the list.
4. Sum up the bits based on position to return an overall base 10 response.

First Iteration — Use Kotlin Lists

Using a list-based approach to solving the bit swapping problem, we can learn a few things about Kotlin’s support for immutable and mutable lists. We will start by creating a new function called swap() that will take the bits in a list where ‘1’ integer represents a binary one and ‘0’ integer represents a binary zero. The swap function will return a new list with the bits swapped.

Notice how a mutableList is created in the body but a List<Int> is returned. The returned value is identified as immutable, using a List interface, where the actual list in the function is defined as mutable to ensure the values can be added.

fun swapUsingLists(originalBits: List<Int>): List<Int> {

    // Construct a mutable list that will hold the swapped bits 
    val newList = mutableListOf<Int>()
    var index = 0

    while (index < originalBits.size) {
        val v1 = originalBits[index]
        val v2 = originalBits[index + 1]
        newList.add(index, v2)
        newList.add(index + 1, v1)
        index += 2
    }
    return newList
}

A main function is created to instantiate a SwapAdjacentBits class, which contains the swapUsingLists() function, and then the swap() function is invoked.

fun main(args: Array<String>) {
    val swab = SwapAdjacentBits()
    val binaryAsList = listOf(0,1,0,1)
    val result = swab.swap(binaryAsList)
    println("Bit swapping calling swap($binaryAsList) results in:         $result")
}

Output after running the application

Bit swapping calling swap([0, 1, 0, 1]) results in: [1, 0, 1, 0]
Process finished with exit code 0

Adding Maths

To expand on this a bit further, we can create another function that will compute the base 10 value for the binary values of our lists before and after swapping occurs.

In order to add up the values, the Kotlin’s Math class is leveraged to obtain the power of each index of the array where binary one is set.

fun computeValue(listOfBits: List<Int>) : Int {

    var sum = 0
    var index2 = 0
    while (index2 < listOfBits.size) {

        val bitValue = listOfBits[index2]
        if (bitValue == 1) {
            sum+= Math.pow(2.0, index2.toDouble()).toInt()
        }
        index2++
    }
    return sum
}

A direct and basic way to compute a value for the set bits is to iterate over the list and where the value is set to one, add the 2^index (2 to the power of index) to a running total. That total value is then returned as the computed sum for the list of bits provided.

For example, when [1 1 0 0]. The computed value would be 2² + 2³, which yields the base 10 value 12.

Extension Functions Anyone?

There is something that can be applied to refactor the swapping of values at this point. In Kotlin, there is the concept of extension functions that can be utilized allowing functions to be applied to existing classes without having to inherit the class. In the case of the mutable list a swap() function can be added to the MutableList class that is private to the implementation.

For example, the swapping logic can be migrated to the function extension on the Kotlin MutableList class.

private fun <T> MutableList<T>.swap(idx1: Int, idx2: Int) {
    val tempValue = this[idx1]
    this[idx1] = this[idx2]
    this[idx2] = tempValue
}

The swap(idx1, idx2) function extension is now usable for the purpose of swapping the index values.

This refactors the swapUsingLists(originalBits:List<Int>) function that takes the original list of bits as input.

Apply Extension Function to swapUsingLists()

Below, the newList, which is a MutableList implemented by Kotlin, exposes the customized swap(idx1, idx2) function. This is extremely powerful when needing functionality that isn’t already provided by a class.

fun swapUsingLists(originalBits: List<Int>): List<Int> {

    val newList = mutableListOf<Int>()
    newList.addAll(originalBits)

    var index = 0
    while (index < originalBits.size) {
        newList.swap(index,index+1)
        index +=2
    }
    return newList
}

So far, the following has been addressed:

• Created a basic class using a direct approach to swapping bits with Kotlin lists.
• Identified a Math function to assist with N to the power of N computations.
• Witnessed the use of the List interface in Kotlin used for working with immutable lists.
• Observed the use of mutableListOf() inline function that is provided by the Kotlin standard library to allow for state change of the list values.
• Learned how to apply Kotlin extension functions.

But knowing more about what Kotlin provides with bitwise operators, the solution to the challenge can be approached in a different manner.

Introducing Bitwise Operators

Using knowledge of Kotlin’s bitwise operations, the problem can be approached differently. It turns out that some “bit manipulators” out there know of ways to reverse bits using bitwise operations. It starts with understanding how the bitwise AND, OR, and SHIFT operations work. In the next steps, we will construct a solution to the challenge using the bitwise operators.

But first, let’s cover the basics of these operations. It’s o.k. if this is a touch overwhelming as binary logic can be confusing when not working with it frequently.

When two bits have a bitwise AND applied, only when both values are 1 will the result be 1. Otherwise, the result will be 0.

0 AND 0 => 0, 0 AND 1 => 0, 1 AND 1 => 1

When two bits have a bitwise OR applied, when one bit is 1 the result will be 1. Otherwise, the result will be 0.

Also, a value can have its bits shifted either left or right by a number of bits, which can change its value. Below the value 1 is shifted right by 1 so the new value becomes 0. In the second example, the number 1 and is shifted left by 1 bit so becomes the value 2.

0001 shifted-right by 1 bit => 0
0001 shifted-left by 1 bit => 2

In Kotlin, the ‘and’, ‘or’, and ‘shift’ are achieved with bitwise operations that are available for Int and Long types. A summary of these operations (obtained from the Kotlinlang.org site) are listed below.

· shl(bits) — signed shift left
· shr(bits) — signed shift right
· ushr(bits) — unsigned shift right
· and(bits) — bitwise and
· or(bits) — bitwise or
· xor(bits) — bitwise xor
· inv() — bitwise inversion

Note: the examples below will use 8-bits as opposed to 4-bits. and the same algorithm can be applied to any number of bits if you have a larger number that requires more than 8 bits to represent.

Remember, 4-bits supported 0–15 base 10 values, and 8-bits will support up to 2⁸-1.
Using the number 19 as an example, the following bit pattern will be used.
[ 0 0 0 1 0 0 1 1 ]
Remember, we know the bits that will be set to 1 by position using base 2 to the power of the index.
2⁰=1, 2¹=2, 2⁴=16, which results in 1+2+16 = 19.

One solution takes the following stepped approach. It begins with locating the even and odd bits.

1. AND the number with even bits set. 
Even bits for 8-bit value: [ 1010 1010 ]

2. Shift the answer to the right by one bit. Becomes alternate spot for the evens.
3. AND the number with odd bits set.
Odd bits for 8-bit value:  [ 0101 0101 ]
4. Shift the answer to the left by one bit. Becomes alternate spot for the odds.
5. OR the results of the even and odd processing to return the result of the bit swapping.

Step #1

Let’s break this down, the even bits for an 8-bit number are defined and then an AND operation is performed with the value (in this case our value=19).

The result is preserving the even bits existing for the number 19. In this case, the second bit is the only one found. Remember, when an AND is performed, the result is one only when both bits are one.

Step #2

Take the result and shift it to the right by one bit. This becomes the alternate spots for the even bits.

This results is [ 00000001 ]

Step #3

The odd bits for an 8-bit number are defined as [ 01010101 ]. Now AND the odd bits with our value = 19.

[ 0101 0101 ] AND [ 0001 0011 ]=> [ 0001 0001 ]

Step #4

Take the result and shift it to the left by one bit. This becomes the alternate spots for the odd bits.

This results in [ 0010 0010 ].

Step #5

OR the two results together having our alternate spots (both odd and even). Remember, when performing an OR, when any bit is one the result is one. Only two zeros result in zero.

[ 0000 0001 ] OR [ 0010 0010 ] = > [0010 0011]

The base 10 value of this bit set is calculate by adding up the bit positions that have one.

2^0 + 2^1 + 2^5 => 1 + 2 + 32 => 35

How can we implement these bitwise operations using these set of steps? It turns out Kotlin provides functionality to perform this efficiently and concisely.

Solution with Kotlin

A function will be created to do this all of this work in an alternate way. The input will be a number of type Long and will return a Long value.

fun alternateSolution(number: Long):Long {
   ...
}

Note: We are using a Long (a 64-bit) type to ensure that any bitwise operations that expand beyond our a 16-bit value are well received.

For the even and odd bit sets, we can specify these values using base 16 (hexadecimal) to make the code and bitwise operations more readable (human friendly).

Base 16 uses sixteen symbols 0–9 to represent zero through nine, and A, B, C, D, E, and F to represent values ten to fifteen.

Since we need the even bits set in a 16-bit number, we use 0xAAAA. The hex value ‘A’ (which is a base 10 value of 10). A is four-bits as (1 0 1 0) in binary, where the second and fourth bits are set.

For a 16-bit number representing all even bits set then all of the positions 2,4,6,8,10,12,14,16 will contain a 1.

val evenBitsSet:Long = 0xAAAA

This will be 1010101010101010 as 16-bits. As for the odd bits, we will use 0x5555 as the number 5 is 0101 in binary.

val oddBitsSet:Long = 0x5555

This will be 0101010101010101 as 16-bits.

In Kotlin, we can now leverage some handy functions to calculate a value. To perform an AND operation in Kotlin, the ‘and’ function can be used from either the Long or Int class. The OR and shift operations are also supported. Below we take the number provided and then AND it with the even bit set (0xAAAA).

number.and(evenBitsSet)

Referring back to the steps in computing the swapped value, the next activity is to shift the results of the AND operation to the right by 1 bit. The Kotlin ‘shr()’ function is used to identify the alternate spots for the evens.

val evenBitsSet:Long = 0xAAAAAAAA
val numberAndedWithEvenBits = number.and(evenBitsSet)
val alternateSpotForEvens = numberAndedWithEvenBits.shr(1)

Using a similar approach, the odd bits identified are shifted left by one bit to identify the alternate spot for odds.

val oddBitsSet:Long = 0x55555555
val numberAndedWithOddBits = number.and(oddBitsSet)
val alternateSpotForOdds = numberAndedWithOddBits.shl(1)

The two alternate bit settings for evens and odds have the OR applied as the final result.

return alternateSpotForEvens.or(alternateSpotForOdds)

The completed solution using the step by step approach looks something like the following.

fun alternateSolution(number: Long):Long {
    val evenBitsSet:Long = 0xAAAAAAAA 
    val oddBitsSet:Long = 0x55555555
    val numberAndedWithEvenBits = number.and(evenBitsSet)
    val alternateSpotForEvens = numberAndedWithEvenBits.shr(1)
    val numberAndedWithOddBits = number.and(oddBitsSet)
    val alternateSpotForOdds = numberAndedWithOddBits.shl(1)
    return alternateSpotForEvens.or(alternateSpotForOdds)
}

Just to take this one step further for simplification, the above can be consolidated into one return statement.

fun alternateSolutionCondensed(number: Long) : Long {
     return ( ((number.and(0xAAAAAAAA))
     .shr(1))
     .or( (number.and(0x55555555)).shl(1)) )
}

Summary

We were able to look at an initial solution taking a direct approach using Kotlin’s list manipulation to calculate the bit swapping value. Along the way, with that approach, we covered some uses of the Math class and extension functions.

The direct approach is technically an accurate way to solve the problem. However, when knowing about the bitwise operations AND, OR, shift-left, and shift-right, the solution can be approached differently (and more efficiently). As a result, an elegant way to solve the problem ended up being about one line of source code in a function.

I hope you enjoyed learning something about Kotlin’s bitwise operations (among some other tidbits)!

Until next time …

References

https://www.topcoder.com/community/data-science/data-science-tutorials/a-bit-of-fun-fun-with-bits/

http://www.geeksforgeeks.org/swap-all-odd-and-even-bits/

http://angrybyte.me/post/154701023805/kotlin-adventures-1

Microsoft Interview Question for Software Engineer / Developers