Skip to main content

Activate all bits of a number

In computing, data is represented in binary format using bits, which are either 0 or 1. Sometimes, it may be necessary to set all the bits of a given number to 1, effectively turning it into the largest possible number with the same number of bits. This process is commonly referred to as "activating" or "setting" all bits.

Introduction to the Problem:

The goal of this article is to explain and implement an algorithm that can activate all the bits of a given number. We will go step-by-step, providing a detailed explanation along with suitable examples to understand the concept thoroughly.

Problem Statement:

Given an input number num, the task is to activate all the bits present in that number. We want to convert the original number to the largest possible number with the same number of bits, where all bits are set to 1.

Explanation with Example:

Let's take an example to illustrate the process. Consider the input number 16 (binary 10000). To activate all bits, we need to turn all the bits on the right of the leftmost 1 bit to 1. So, the binary representation of the largest possible number with the same number of bits would be 11111, which is equal to 31 in decimal.

Another example is the number 99 (binary 1100011). Activating all the bits will yield 1111111, which is 127 in decimal.

Similarly, for the number 9999999 (binary 100110001001011001111111), activating all bits will result in 111111111111111111111111, which is 16777215 in decimal.

Pseudocode:

The following pseudocode outlines the algorithm to activate all bits of a number:

activeAllBits(num):
    n = num
    n = n | n >> 1
    n = n | n >> 2
    n = n | n >> 4
    n = n | n >> 8
    n = n | n >> 16
    return n

Algorithm Explanation:

  1. We start by defining the activeAllBits function that takes an input num, the number whose bits we want to activate.
  2. We create a temporary variable n and set it equal to the input number num.
  3. To activate all the bits, we use bitwise OR (|) operator. We perform a series of bitwise operations by right-shifting n by different positions (1, 2, 4, 8, and 16) and then OR the result with n. This process effectively sets all the bits on the right of the leftmost 1 bit to 1.
  4. Finally, we return the value of n, which now represents the largest possible number with all bits activated.

Output Explanation:

For the given examples in the code:

  1. For the number 16, the largest possible number with all bits activated is 31.
  2. For the number 99, the largest possible number with all bits activated is 127.
  3. For the number 9999999, the largest possible number with all bits activated is 16777215.

Code Solution

// C Program 
// Activate all bits of a number
#include <stdio.h>

// Active all the bits of present in a number
void activeAllBits(int num)
{
	int n = num;
	n = n | n >> 1;
	n = n | n >> 2;
	n = n | n >> 4;
	n = n | n >> 8;
	n = n | n >> 16;
	// Display calculated result
	printf(" Number : %d", num);
	printf("\n After Active : %d\n", n);
}
int main()
{
	// (16) 10000 => 11111 (31)
	activeAllBits(16);
	// (99) 1100011 => 1111111 (127) 
	activeAllBits(99);
	// (9999999)    100110001001011001111111 =>
	// (16777215)   111111111111111111111111
	activeAllBits(9999999);
	return 0;
}

Output

 Number : 16
 After Active : 31
 Number : 99
 After Active : 127
 Number : 9999999
 After Active : 16777215
/*
  Java Program for
  Activate all bits of a number
*/
public class BitActivation
{
	// Active all the bits of present in a number
	public void activeAllBits(int num)
	{
		int n = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		// Display calculated result
		System.out.print(" Number : " + num);
		System.out.print("\n After Active : " + n + "\n");
	}
	public static void main(String[] args)
	{
		BitActivation task = new BitActivation();
		// (16) 10000 => 11111 (31)
		task.activeAllBits(16);
		// (99) 1100011 => 1111111 (127) 
		task.activeAllBits(99);
		// (9999999)    100110001001011001111111 =>
		// (16777215)   111111111111111111111111
		task.activeAllBits(9999999);
	}
}

Output

 Number : 16
 After Active : 31
 Number : 99
 After Active : 127
 Number : 9999999
 After Active : 16777215
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for
  Activate all bits of a number
*/
class BitActivation
{
	public:
		// Active all the bits of present in a number
		void activeAllBits(int num)
		{
			int n = num;
			n = n | n >> 1;
			n = n | n >> 2;
			n = n | n >> 4;
			n = n | n >> 8;
			n = n | n >> 16;
			// Display calculated result
			cout << " Number : " << num;
			cout << "\n After Active : " << n << "\n";
		}
};
int main()
{
	BitActivation task = BitActivation();
	// (16) 10000 => 11111 (31)
	task.activeAllBits(16);
	// (99) 1100011 => 1111111 (127)
	task.activeAllBits(99);
	// (9999999)    100110001001011001111111 =>
	// (16777215)   111111111111111111111111
	task.activeAllBits(9999999);
	return 0;
}

Output

 Number : 16
 After Active : 31
 Number : 99
 After Active : 127
 Number : 9999999
 After Active : 16777215
// Include namespace system
using System;
/*
  C# Program for
  Activate all bits of a number
*/
public class BitActivation
{
	// Active all the bits of present in a number
	public void activeAllBits(int num)
	{
		int n = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		// Display calculated result
		Console.Write(" Number : " + num);
		Console.Write("\n After Active : " + n + "\n");
	}
	public static void Main(String[] args)
	{
		BitActivation task = new BitActivation();
		// (16) 10000 => 11111 (31)
		task.activeAllBits(16);
		// (99) 1100011 => 1111111 (127)
		task.activeAllBits(99);
		// (9999999)    100110001001011001111111 =>
		// (16777215)   111111111111111111111111
		task.activeAllBits(9999999);
	}
}

Output

 Number : 16
 After Active : 31
 Number : 99
 After Active : 127
 Number : 9999999
 After Active : 16777215
<?php
/*
  Php Program for
  Activate all bits of a number
*/
class BitActivation
{
	// Active all the bits of present in a number
	public	function activeAllBits($num)
	{
		$n = $num;
		$n = $n | $n >> 1;
		$n = $n | $n >> 2;
		$n = $n | $n >> 4;
		$n = $n | $n >> 8;
		$n = $n | $n >> 16;
		// Display calculated result
		echo " Number : ". $num;
		echo "\n After Active : ". $n ."\n";
	}
}

function main()
{
	$task = new BitActivation();
	// (16) 10000 => 11111 (31)
	$task->activeAllBits(16);
	// (99) 1100011 => 1111111 (127)
	$task->activeAllBits(99);
	// (9999999)    100110001001011001111111 =>
	// (16777215)   111111111111111111111111
	$task->activeAllBits(9999999);
}
main();

Output

 Number : 16
 After Active : 31
 Number : 99
 After Active : 127
 Number : 9999999
 After Active : 16777215
/*
  Node Js Program for
  Activate all bits of a number
*/
class BitActivation
{
	// Active all the bits of present in a number
	activeAllBits(num)
	{
		var n = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		// Display calculated result
		process.stdout.write(" Number : " + num);
		process.stdout.write("\n After Active : " + n + "\n");
	}
}

function main()
{
	var task = new BitActivation();
	// (16) 10000 => 11111 (31)
	task.activeAllBits(16);
	// (99) 1100011 => 1111111 (127)
	task.activeAllBits(99);
	// (9999999)    100110001001011001111111 =>
	// (16777215)   111111111111111111111111
	task.activeAllBits(9999999);
}
main();

Output

 Number : 16
 After Active : 31
 Number : 99
 After Active : 127
 Number : 9999999
 After Active : 16777215
#   Python 3 Program for
#   Activate all bits of a number

class BitActivation :
	#  Active all the bits of present in a number
	def activeAllBits(self, num) :
		n = num
		n = n | n >> 1
		n = n | n >> 2
		n = n | n >> 4
		n = n | n >> 8
		n = n | n >> 16
		#  Display calculated result
		print(" Number : ", num, end = "")
		print("\n After Active : ", n )
	

def main() :
	task = BitActivation()
	#  (16) 10000 => 11111 (31)
	task.activeAllBits(16)
	#  (99) 1100011 => 1111111 (127) 
	task.activeAllBits(99)
	#  (9999999)    100110001001011001111111 =>
	#  (16777215)   111111111111111111111111
	task.activeAllBits(9999999)

if __name__ == "__main__": main()

Output

 Number :  16
 After Active :  31
 Number :  99
 After Active :  127
 Number :  9999999
 After Active :  16777215
#   Ruby Program for
#   Activate all bits of a number

class BitActivation 
	#  Active all the bits of present in a number
	def activeAllBits(num) 
		n = num
		n = n | n >> 1
		n = n | n >> 2
		n = n | n >> 4
		n = n | n >> 8
		n = n | n >> 16
		#  Display calculated result
		print(" Number : ", num)
		print("\n After Active : ", n ,"\n")
	end

end

def main() 
	task = BitActivation.new()
	#  (16) 10000 => 11111 (31)
	task.activeAllBits(16)
	#  (99) 1100011 => 1111111 (127) 
	task.activeAllBits(99)
	#  (9999999)    100110001001011001111111 =>
	#  (16777215)   111111111111111111111111
	task.activeAllBits(9999999)
end

main()

Output

 Number : 16
 After Active : 31
 Number : 99
 After Active : 127
 Number : 9999999
 After Active : 16777215
/*
  Scala Program for
  Activate all bits of a number
*/
class BitActivation
{
	// Active all the bits of present in a number
	def activeAllBits(num: Int): Unit = {
		var n: Int = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		// Display calculated result
		print(" Number : " + num);
		print("\n After Active : " + n + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: BitActivation = new BitActivation();
		// (16) 10000 => 11111 (31)
		task.activeAllBits(16);
		// (99) 1100011 => 1111111 (127)
		task.activeAllBits(99);
		// (9999999)    100110001001011001111111 =>
		// (16777215)   111111111111111111111111
		task.activeAllBits(9999999);
	}
}

Output

 Number : 16
 After Active : 31
 Number : 99
 After Active : 127
 Number : 9999999
 After Active : 16777215
/*
  Swift 4 Program for
  Activate all bits of a number
*/
class BitActivation
{
	// Active all the bits of present in a number
	func activeAllBits(_ num: Int)
	{
		var n: Int = num;
		n = n | n >> 1;
		n = n | n >> 2;
		n = n | n >> 4;
		n = n | n >> 8;
		n = n | n >> 16;
		// Display calculated result
		print(" Number : ", num, terminator: "");
		print("\n After Active : ", n );
	}
}
func main()
{
	let task: BitActivation = BitActivation();
	// (16) 10000 => 11111 (31)
	task.activeAllBits(16);
	// (99) 1100011 => 1111111 (127)
	task.activeAllBits(99);
	// (9999999)    100110001001011001111111 =>
	// (16777215)   111111111111111111111111
	task.activeAllBits(9999999);
}
main();

Output

 Number :  16
 After Active :  31
 Number :  99
 After Active :  127
 Number :  9999999
 After Active :  16777215
/*
  Kotlin Program for
  Activate all bits of a number
*/
class BitActivation
{
	// Active all the bits of present in a number
	fun activeAllBits(num: Int): Unit
	{
		var n: Int = num;
		n = n or (n shr 1);
		n = n or (n shr 2);
		n = n or (n shr 4);
		n = n or (n shr 8);
		n = n or (n shr 16);
		// Display calculated result
		print(" Number : " + num);
		print("\n After Active : " + n + "\n");
	}
}
fun main(args: Array <String> ): Unit
{
	var task: BitActivation = BitActivation();
	// (16) 10000 => 11111 (31)
	task.activeAllBits(16);
	// (99) 1100011 => 1111111 (127)
	task.activeAllBits(99);
	// (9999999)    100110001001011001111111 =>
	// (16777215)   111111111111111111111111
	task.activeAllBits(9999999);
}

Output

 Number : 16
 After Active : 31
 Number : 99
 After Active : 127
 Number : 9999999
 After Active : 16777215

Time Complexity:

The time complexity of the algorithm is O(1) because the number of operations remains constant, regardless of the input number size.

In this article explained the concept of activating all bits of a number and provided a step-by-step implementation algorithm. We discussed the problem, provided suitable examples, and explained the pseudocode and algorithm in detail. The algorithm efficiently activates all the bits of a given number, converting it into the largest possible number with the same number of bits, where all bits are set to 1.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment