Complement of Base 10 Number (medium)

Press + to interact

Python 3.5

def calculate_bitwise_complement(num):
  # count number of total bits in 'num'
  bit_count, n = 0, num
  while n > 0:
    bit_count += 1
    n = n >> 1
  # for a number which is a complete power of '2' i.e., it can be written as pow(2, n), if we
  # subtract '1' from such a number, we get a number which has 'n' least significant bits set to '1'.
  # For example, '4' which is a complete power of '2', and '3' (which is one less than 4) has a binary
  # representation of '11' i.e., it has '2' least significant bits set to '1'
  all_bits_set = pow(2, bit_count) - 1
  # from the solution description: complement = number ^ all_bits_set
  return num ^ all_bits_set
print('Bitwise complement is: ' + str(calculate_bitwise_complement(8)))
print('Bitwise complement is: ' + str(calculate_bitwise_complement(10)))

Step-by-step solution construction

In binary, the complement of a number is what we get when we change every 0 to 1, and 1 to 0. For example, the complement of 1000 will be 0111.

As explained in the course lesson, keeping the XOR rules in mind, the complement of a number is equal to number XOR all_bits_set.

The first step in our algorithm is to calculate the number of bits required to represent the input number. For example, 8 in binary is 1000, which uses 4 bits. Similarly, 64 in binary is 1000000, which has 7 bits.

To get the bit count, we right shift our input number by 1 until it becomes zero. The bit count is incremented by 1 with every right shift. Consider the following:

Input: 8
Representation in binary: 1000

Bit count incremented: 1
Number after right shift: 0100

Bit count incremented: 2
Number after right shift: 0010

Bit count incremented: 3
Number after right shift: 0001

Bit count incremented: 4
Number after right shift: 0000

Since the number has become 0, we stop here. The bit count is the number of bits we need for representing the input number, which in this case is 4.

Press + to interact

Python 3.5

def toBinary(n):
  return'{0:04b}'.format(n)
def calculate_bitwise_complement(num):
  # count number of total bits in 'num'
  bit_count, n = 0, num
  print("Input number: ", n, "(", toBinary(n), ")", sep = "")
  print("bit_count: ", bit_count, sep = "")
  print("")
  i=1
  while n > 0:
    print("Loop iteration: ", i, sep = "")
    i+=1
    bit_count += 1
    print("\tIncrementing bit_count: ", bit_count, sep = "")
    n = n >> 1
    print("\tRight shifting n by 1")
    print("\t\tUpdated n: ", n, "(", toBinary(n), ")", sep = "")
    print("")
  print("Since the number has now become zero, we stop here.\n")
input = [8,10]
for i in input:
  print('Bitwise complement of', i, 'is:',  calculate_bitwise_complement(i))
  print(("-"*100)+"\n")

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}

The next step is to calculate all_bits_set. Set bits are the ones that are equal to 1. For instance, 0111 has 3 set bits, while 1000 has 1 set bit. The variable all_bits_set will store the number of set bits in our number.

For a number, $y$ , that is a complete power of two, that is, it can be written as $y = 2^n$ , the number $y - 1$ will have $n$ least significant bits set to 1.

Consider an example where $y = 4$ . Since $4$ can be written as $2^2$ , we can say it is a complete power of $2$ , and in this case, $n = 2$ . For the number $y - 1$ , that is, $4 - 1 = 3$ , the binary representation will have $n = 2$ least significant bits set to 1. If we take a look at the binary representation of $3$ , which is $0011$ , we notice that the above statement is true.

Similarly, consider another example: $y = 8$ . This can be written as $y = 2^n$ , where $n = 3$ . So, the number $y - 1 = 8 - 1 = 7$ will have $3$ least significant bits set to $1$ . Therefore, it’s binary will be $0111$ .

Using this approach, we’ll calculate the number of set bits in our input.

Press + to interact

Python 3.5

def toBinary(n):
  return'{0:04b}'.format(n)
def calculate_bitwise_complement(num):
  # count number of total bits in 'num'
  bit_count, n = 0, num
  print("Input number: ", n, "(", toBinary(n), ")", sep = "")
  print("bit_count: ", bit_count, sep = "")
  print("")
  i=1
  while n > 0:
    print("Loop iteration: ", i, sep = "")
    i+=1
    bit_count += 1
    print("\tIncrementing bit_count: ", bit_count, sep = "")
    n = n >> 1
    print("\tRight shifting n by 1")
    print("\t\tUpdated n: ", n, "(", toBinary(n), ")", sep = "")
    print("")
  print("Since the number has now become zero, we stop here.\n")
  
  print("Calculating the number with all bits set:")
  temp = pow(2, bit_count)
  print("\t2 to the power of bit_count: ", temp, "(", toBinary(temp), ")", sep = "")
  print("\tSubtracting 1 from the result: ", temp, " - ", 1, " = ", temp - 1, "(", toBinary(temp-1), ")", sep = "")
  all_bits_set = pow(2, bit_count) - 1
  print("\tNumber with all bits set: ", all_bits_set, "(", toBinary(all_bits_set), ")\n", sep = "")
input = [8,10]
for i in input:
  print('Bitwise complement of', i, 'is:',  calculate_bitwise_complement(i))
  print(100*"-")

Our last step is to compute the complement using the formula derived in the lesson.

complement = num ^ all_bits_set

We already have num and all_bits_set. Now we’ll just take their XOR and return the value.

Press + to interact

Python 3.5

def toBinary(n):
  return'{0:04b}'.format(n)
def calculate_bitwise_complement(num):
  # count number of total bits in 'num'
  bit_count, n = 0, num
  print("Input number: ", n, "(", toBinary(n), ")", sep = "")
  print("bit_count: ", bit_count, sep = "")
  print("")
  i=1
  while n > 0:
    print("Loop iteration: ", i, sep = "")
    i+=1
    bit_count += 1
    print("\tIncrementing bit_count: ", bit_count, sep = "")
    n = n >> 1
    print("\tRight shifting n by 1")
    print("\t\tUpdated n: ", n, "(", toBinary(n), ")", sep = "")
    print("")
  print("Since the number has now become zero, we stop here.\n")
  
  print("Calculating the number with all bits set:")
  temp = pow(2, bit_count)
  print("\t2 to the power of bit_count: ", temp, "(", toBinary(temp), ")", sep = "")
  print("\tSubtracting 1 from the result: ", temp, " - ", 1, " = ", temp - 1, "(", toBinary(temp-1), ")", sep = "")
  all_bits_set = pow(2, bit_count) - 1
  print("\tNumber with all bits set: ", all_bits_set, "(", toBinary(all_bits_set), ")\n", sep = "")
  print("Computing the complement of the input: ", num,"(", toBinary(num), ")", sep = "")
  print("\tTaking XOR: ", num, " XOR ", all_bits_set, " = ", num ^ all_bits_set, "(", toBinary(num ^ all_bits_set), ")\n", sep = "" )
  return num ^ all_bits_set
input = [8,10]
for i in input:
  print('Bitwise complement of', i, 'is:',  calculate_bitwise_complement(i))
  print(("-"*100)+"\n")

Iteration number	Line number	bit_count	n	num	all_bits_set	num ^ all_bits_set
-	3	0	8	8	-	-
1	4-6	1	4	8	-	-
2	4-6	2	2	8	-	-
3	4-6	3	1	8	-	-
4	4-6	4	0	8	-	-
-	12	4	0	8	15	-
-	15	4	0	8	15	7

Iteration number	Line number	bit_count	n	num	all_bits_set	num ^ all_bits_set
-	3	0	10	10	-	-
1	4-6	1	5	10	-	-
2	4-6	2	2	10	-	-
3	4-6	3	1	10	-	-
4	4-6	4	0	10	-	-
-	12	4	0	10	15	-
-	15	4	0	10	15	5

Pattern: Sliding Window

Pattern: Two Pointers

Pattern: Fast & Slow pointers

Pattern: In-place Reversal of a LinkedList

Pattern: Tree Breadth First Search

Pattern: Tree Depth First Search

Pattern: Modified Binary Search

Pattern: Top 'K' Elements

Pattern: K-way merge

Pattern: Subsets

Pattern : 0/1 Knapsack (Dynamic Programming)

Pattern: Topological Sort

Pattern: Two Heaps

Pattern: Cyclic Sort

Pattern: Bitwise XOR

Pattern: Merge Intervals

Complement of Base 10 Number (medium)

Dry-run templates

Sample input #1

Sample input #2

Step-by-step solution construction