Kotlin – Bitwise Operations & 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.

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. 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.

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 you had 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^4) - 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 Kafka 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.

Create a list of bit settings to represent a number.
Construct a list that will hold the swapped bits.
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.
Sum up the bits based on position to return an overall base 10 response.

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.

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

// Construct a mutable list that will hold the swapped bits
val newList = mutableListOf<Int>()
var index = 0
// Loop over the original bits and swap the bits set by set until reached the end of the list
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 class and main function are created to instantiate the SwapAdjacentBits and invoke the swap() function.

class SwapAdjacentBits

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

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, we leverage Kotlin’s Math class to obtain the power of each index of the array where the 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 basic way to compute a value for bits set is to iterate over the list of bits 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 we have [1 1 0 0]. The computed value would be 2^2 + 2^3, which yields the base 10 value 12.

There is something we can do 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 our mutable list we can add a swap() function to the MutableList class that is private to our implementation. For example, the swapping logic can be migrated to the function extension on the 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 our purpose of swapping the index values. This refactors our swap(originalBits:List<Int>) function that takes the original list of bits as input.

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 swap(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
}

All of this is great, and so far, we’ve accomplished the following:

Created a basic program 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.
Learned about and how to apply Kotlin extension functions.

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

An Alternate Solution – Introducing Bit Operations

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.

AND Operation

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

OR Operation

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

0 OR 1 => 1, 1 OR 1 => 1

Shift Operation

A number can have its bits shifted either left or right by a number of bits.

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

We will use some of the above Kotlin bitwise operations to solve the bit swapping problem. One approach begins with finding the even and odd bits that are set for the number provided. The examples below will use 8-bits as opposed to 4-bits. 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^8 – 1 base 10 values.

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 one by position of value by using base 2 to the power of the index.

2^0=1, 2^1=2, 2^4=16, which results in 1+2+16 = 19.

One solution to swapping the bits performs the following steps:

AND the number with even bits set.
Shift the answer to the right by one bit. Becomes alternate spot for the evens.
AND the number with odd bits set.
Shift the answer to the left by one bit. Becomes alternate spot for the odds.
OR the results of the even and odd processing.
Even bit processing with 8-bit 10101010

0 0 0 1 0 0 1 1 (19)
1 0 1 0 1 0 1 0 (0xAA)
------------------- (AND)
0 0 0 0 0 0 1 0
>> 1
0 0 0 0 0 0 0 1

Odd bit processing with 8-bit 01010101
0 0 0 1 0 0 1 1 (19)
0 1 0 1 0 1 0 1 (0X55)
------------------- (AND)
0 0 0 1 0 0 0 1
<< 1
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 1
------------------ (OR)
0 0 1 0 0 0 1 1

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. Let’s begin coding the solution using this knowledge.

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 following implementation can be used as a one liner.

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. This is technically an accurate way to provide a solution. However, when knowing about the bitwise operations AND, OR, shift-left, and shift-right, the solution can be approached differently. As a result, a very efficient way to solve the problem ended up being one line of source code in a function. I hope you enjoyed learning something about Kotlin’s bitwise operations and how they can be used.

Until next time …