educative.io

An O(1) solution

Courses
,
#1 
def calculate_bitwise_complement(n):
  if n <= 0:
    return n
  nbits = int(math.log(n,2)) + 1
  mask = (1 << nbits) - 1
  return n ^ mask
#2

Great solution @Guy_Rauscher! The following could be the java version:

    public static int log(int x, int base) {
      return (int)(Math.log(x) / Math.log(base));
    }

    public static int bitwiseComplement(int num) {
      // count number of total bits in 'num'
      int bitCount = log(num, 2) + 1;

      int all_bits_set = (1 << bitCount) - 1;

      // from the solution description: complement = number ^ all_bits_set
      return num ^ all_bits_set;
    }
1 Like
#3

Agreed, there is no need for a loop when you can get the number of bits needed with log2(n). My version:

import math

def calculate_bitwise_complement(n):
  all_ones = 2 ** (math.floor(math.log2(n)) + 1) - 1
  return all_ones ^ n