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:
- We start by defining the
activeAllBits
function that takes an inputnum
, the number whose bits we want to activate. - We create a temporary variable
n
and set it equal to the input numbernum
. - To activate all the bits, we use bitwise OR (
|
) operator. We perform a series of bitwise operations by right-shiftingn
by different positions (1, 2, 4, 8, and 16) and then OR the result withn
. This process effectively sets all the bits on the right of the leftmost 1 bit to 1. - 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:
- For the number
16
, the largest possible number with all bits activated is31
. - For the number
99
, the largest possible number with all bits activated is127
. - For the number
9999999
, the largest possible number with all bits activated is16777215
.
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.
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