Skip to main content

Check if a number has two adjacent active bits

Determine whether a given integer has two adjacent active bits (1s) in its binary representation. In other words, we want to check if there are two consecutive 1s in the binary form of the number. This involves bitwise operations to analyze the binary representation and identify the presence of adjacent active bits.

Check if two adjacent bits are set in a number

Problem Statement and Description

Given an integer num, the task is to determine whether there are two adjacent active bits (1s) in its binary representation. We need to perform bitwise operations to check if there is a consecutive occurrence of two 1s in the binary form of the number.

Example

Consider the number 12. In binary form, it is represented as 1100. This number contains two adjacent active bits (1s) at positions 2 and 3. Therefore, the expected output for this example should be "Adjacent active bit exist".

  1. For the number 12:

    • Binary representation: 1100
    • Two adjacent active bits exist at positions 2 and 3.
    • The output is "Number: 12\nAdjacent active bit exist".

  2. For the number 34:

    • Binary representation: 100010
    • No two adjacent active bits are present.
    • The output is "Number: 34\nAdjacent active bit not exist".

  3. For the number -12:

    • Binary representation: (∞11110100)
    • Two adjacent active bits exist at positions 2 and 3 (considering 32-bit representation).
    • The output is "Number: -12\nAdjacent active bit exist".

  4. For the number 7:

    • Binary representation: 111
    • Two adjacent active bits exist.
    • The output is "Number: 7\nAdjacent active bit exist".

  5. For the number 21:

    • Binary representation: 10101
    • No two adjacent active bits are present.
    • The output is "Number: 21\nAdjacent active bit not exist".

Idea to Solve the Problem

The key idea to solve this problem is to use bitwise operations to check if there are two adjacent active bits in the binary representation of the given number. We can shift the number to the right by one position and perform a bitwise AND operation with the original number. If the result is greater than zero, it means that two adjacent active bits exist. Additionally, if the given number is negative, it will have a sign bit that may affect the result, so we need to handle that case as well.

Pseudocode

Here's the pseudocode for the algorithm:

function adjacentActiveBit(num):
    print "Number: ", num
    if num < 0 or (num & (num >> 1)) > 0:
        print "Adjacent active bit exist"
    else:
        print "Adjacent active bit not exist"

Algorithm Explanation

  1. The function adjacentActiveBit(num) takes an integer num as input.
  2. It prints the given number.
  3. It checks if the given number is negative (num < 0) or if the result of (num & (num >> 1)) is greater than zero. The expression (num & (num >> 1)) checks for the presence of two adjacent active bits using bitwise operations.
  4. If either of the conditions is met, it means that two adjacent active bits exist, and it prints "Adjacent active bit exist".
  5. Otherwise, it prints "Adjacent active bit not exist".

Code Solution

// C Program 
// Check if a number has two adjacent active bits
#include <stdio.h>

// Check that two adjacent set bits exist in given number
void adjacentActiveBit(int num)
{
	// Display given number
	printf("\n Number : %d", num);
	// Shift the given number by one on left side and perform bitwise & operation
	if (num < 0 || (num & (num >> 1)) > 0)
	{
		// If result are greater than zero
		// Or num less than zero
		printf("\n Adjacent active bit exist\n");
	}
	else
	{
		printf("\n Adjacent active bit not exist\n");
	}
}
int main(int argc, char
	const *argv[])
{
	// Test Cases
	// 12 (1100)
	adjacentActiveBit(12);
	// 34 (100010)
	adjacentActiveBit(34);
	// -12 (∞11110100)
	adjacentActiveBit(-12);
	// 7 (111)
	adjacentActiveBit(7);
	// 21 (00010101)
	adjacentActiveBit(21);
	return 0;
}

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist
/*
  Java Program 
  Check if a number has two adjacent active bits
*/
public class BitPosition
{
	// Check that two adjacent set bits exist in given number
	public void adjacentActiveBit(int num)
	{
		// Display given number
		System.out.print("\n Number : " + num);
		// Shift the given number by one on left side and perform bitwise & operation
		if (num < 0 || ((num & (num >> 1)) > 0))
		{
			// If result are greater than zero 
			// Or num less than zero
			System.out.print("\n Adjacent active bit exist\n");
		}
		else
		{
			System.out.print("\n Adjacent active bit not exist\n");
		}
	}
	public static void main(String[] args)
	{
		BitPosition task = new BitPosition();
		// Test Cases
		// 12 (1100)
		task.adjacentActiveBit(12);
		// 34 (100010)
		task.adjacentActiveBit(34);
		// -12 (∞11110100)
		task.adjacentActiveBit(-12);
		// 7 (111)
		task.adjacentActiveBit(7);
		// 21 (00010101)
		task.adjacentActiveBit(21);
	}
}

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist
// Include header file
#include <iostream>
using namespace std;
/*
  C++ Program 
  Check if a number has two adjacent active bits
*/
class BitPosition
{
	public:
		// Check that two adjacent set bits exist in given number
		void adjacentActiveBit(int num)
		{
			// Display given number
			cout << "\n Number : " << num;
			// Shift the given number by one on left side and perform bitwise &operation
			if (num < 0 || ((num &(num >> 1)) > 0))
			{
				// If result are greater than zero
				// Or num less than zero
				cout << "\n Adjacent active bit exist\n";
			}
			else
			{
				cout << "\n Adjacent active bit not exist\n";
			}
		}
};
int main()
{
	BitPosition task = BitPosition();
	// Test Cases
	// 12 (1100)
	task.adjacentActiveBit(12);
	// 34 (100010)
	task.adjacentActiveBit(34);
	// -12 (∞11110100)
	task.adjacentActiveBit(-12);
	// 7 (111)
	task.adjacentActiveBit(7);
	// 21 (00010101)
	task.adjacentActiveBit(21);
	return 0;
}

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist
// Include namespace system
using System;
/*
  C# Program 
  Check if a number has two adjacent active bits
*/
public class BitPosition
{
	// Check that two adjacent set bits exist in given number
	public void adjacentActiveBit(int num)
	{
		// Display given number
		Console.Write("\n Number : " + num);
		// Shift the given number by one on left side and perform bitwise & operation
		if (num < 0 || ((num & (num >> 1)) > 0))
		{
			// If result are greater than zero
			// Or num less than zero
			Console.Write("\n Adjacent active bit exist\n");
		}
		else
		{
			Console.Write("\n Adjacent active bit not exist\n");
		}
	}
	public static void Main(String[] args)
	{
		BitPosition task = new BitPosition();
		// Test Cases
		// 12 (1100)
		task.adjacentActiveBit(12);
		// 34 (100010)
		task.adjacentActiveBit(34);
		// -12 (∞11110100)
		task.adjacentActiveBit(-12);
		// 7 (111)
		task.adjacentActiveBit(7);
		// 21 (00010101)
		task.adjacentActiveBit(21);
	}
}

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist
<?php
/*
  Php Program 
  Check if a number has two adjacent active bits
*/
class BitPosition
{
	// Check that two adjacent set bits exist in given number
	public	function adjacentActiveBit($num)
	{
		// Display given number
		echo "\n Number : ". $num;
		// Shift the given number by one on left side and perform bitwise & operation
		if ($num < 0 || (($num & ($num >> 1)) > 0))
		{
			// If result are greater than zero
			// Or num less than zero
			echo "\n Adjacent active bit exist\n";
		}
		else
		{
			echo "\n Adjacent active bit not exist\n";
		}
	}
}

function main()
{
	$task = new BitPosition();
	// Test Cases
	// 12 (1100)
	$task->adjacentActiveBit(12);
	// 34 (100010)
	$task->adjacentActiveBit(34);
	// -12 (∞11110100)
	$task->adjacentActiveBit(-12);
	// 7 (111)
	$task->adjacentActiveBit(7);
	// 21 (00010101)
	$task->adjacentActiveBit(21);
}
main();

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist
/*
  Node Js Program 
  Check if a number has two adjacent active bits
*/
class BitPosition
{
	// Check that two adjacent set bits exist in given number
	adjacentActiveBit(num)
	{
		// Display given number
		process.stdout.write("\n Number : " + num);
		// Shift the given number by one on left side and perform bitwise & operation
		if (num < 0 || ((num & (num >> 1)) > 0))
		{
			// If result are greater than zero
			// Or num less than zero
			process.stdout.write("\n Adjacent active bit exist\n");
		}
		else
		{
			process.stdout.write("\n Adjacent active bit not exist\n");
		}
	}
}

function main()
{
	var task = new BitPosition();
	// Test Cases
	// 12 (1100)
	task.adjacentActiveBit(12);
	// 34 (100010)
	task.adjacentActiveBit(34);
	// -12 (∞11110100)
	task.adjacentActiveBit(-12);
	// 7 (111)
	task.adjacentActiveBit(7);
	// 21 (00010101)
	task.adjacentActiveBit(21);
}
main();

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist
#   Python 3 Program 
#   Check if a number has two adjacent active bits

class BitPosition :
	#  Check that two adjacent set bits exist in given number
	def adjacentActiveBit(self, num) :
		#  Display given number
		print("\n Number : ", num, end = "")
		#  Shift the given number by one on left side and perform bitwise & operation
		if (num < 0 or((num & (num >> 1)) > 0)) :
			#  If result are greater than zero 
			#  Or num less than zero
			print("\n Adjacent active bit exist")
		else :
			print("\n Adjacent active bit not exist")
		
	

def main() :
	task = BitPosition()
	#  Test Cases
	#  12 (1100)
	task.adjacentActiveBit(12)
	#  34 (100010)
	task.adjacentActiveBit(34)
	#  -12 (∞11110100)
	task.adjacentActiveBit(-12)
	#  7 (111)
	task.adjacentActiveBit(7)
	#  21 (00010101)
	task.adjacentActiveBit(21)

if __name__ == "__main__": main()

Output

 Number :  12
 Adjacent active bit exist

 Number :  34
 Adjacent active bit not exist

 Number :  -12
 Adjacent active bit exist

 Number :  7
 Adjacent active bit exist

 Number :  21
 Adjacent active bit not exist
#   Ruby Program 
#   Check if a number has two adjacent active bits

class BitPosition 
	#  Check that two adjacent set bits exist in given number
	def adjacentActiveBit(num) 
		#  Display given number
		print("\n Number : ", num)
		#  Shift the given number by one on left side and perform bitwise & operation
		if (num < 0 || ((num & (num >> 1)) > 0)) 
			#  If result are greater than zero 
			#  Or num less than zero
			print("\n Adjacent active bit exist\n")
		else 
			print("\n Adjacent active bit not exist\n")
		end

	end

end

def main() 
	task = BitPosition.new()
	#  Test Cases
	#  12 (1100)
	task.adjacentActiveBit(12)
	#  34 (100010)
	task.adjacentActiveBit(34)
	#  -12 (∞11110100)
	task.adjacentActiveBit(-12)
	#  7 (111)
	task.adjacentActiveBit(7)
	#  21 (00010101)
	task.adjacentActiveBit(21)
end

main()

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist

/*
  Scala Program 
  Check if a number has two adjacent active bits
*/
class BitPosition
{
	// Check that two adjacent set bits exist in given number
	def adjacentActiveBit(num: Int): Unit = {
		// Display given number
		print("\n Number : " + num);
		// Shift the given number by one on left side and perform bitwise & operation
		if (num < 0 || ((num & (num >> 1)) > 0))
		{
			// If result are greater than zero
			// Or num less than zero
			print("\n Adjacent active bit exist\n");
		}
		else
		{
			print("\n Adjacent active bit not exist\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: BitPosition = new BitPosition();
		// Test Cases
		// 12 (1100)
		task.adjacentActiveBit(12);
		// 34 (100010)
		task.adjacentActiveBit(34);
		// -12 (∞11110100)
		task.adjacentActiveBit(-12);
		// 7 (111)
		task.adjacentActiveBit(7);
		// 21 (00010101)
		task.adjacentActiveBit(21);
	}
}

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist
/*
  Swift 4 Program 
  Check if a number has two adjacent active bits
*/
class BitPosition
{
	// Check that two adjacent set bits exist in given number
	func adjacentActiveBit(_ num: Int)
	{
		// Display given number
		print("\n Number : ", num, terminator: "");
		// Shift the given number by one on left side and perform bitwise & operation
		if (num < 0 || ((num & (num >> 1)) > 0))
		{
			// If result are greater than zero
			// Or num less than zero
			print("\n Adjacent active bit exist");
		}
		else
		{
			print("\n Adjacent active bit not exist");
		}
	}
}
func main()
{
	let task: BitPosition = BitPosition();
	// Test Cases
	// 12 (1100)
	task.adjacentActiveBit(12);
	// 34 (100010)
	task.adjacentActiveBit(34);
	// -12 (∞11110100)
	task.adjacentActiveBit(-12);
	// 7 (111)
	task.adjacentActiveBit(7);
	// 21 (00010101)
	task.adjacentActiveBit(21);
}
main();

Output

 Number :  12
 Adjacent active bit exist

 Number :  34
 Adjacent active bit not exist

 Number :  -12
 Adjacent active bit exist

 Number :  7
 Adjacent active bit exist

 Number :  21
 Adjacent active bit not exist
/*
  Kotlin Program 
  Check if a number has two adjacent active bits
*/
class BitPosition
{
	// Check that two adjacent set bits exist in given number
	fun adjacentActiveBit(num: Int): Unit
	{
		// Display given number
		print("\n Number : " + num);
		// Shift the given number by one on left side and perform bitwise & operation
		if (num < 0 || ((num and(num shr 1)) > 0))
		{
			// If result are greater than zero
			// Or num less than zero
			print("\n Adjacent active bit exist\n");
		}
		else
		{
			print("\n Adjacent active bit not exist\n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: BitPosition = BitPosition();
	// Test Cases
	// 12 (1100)
	task.adjacentActiveBit(12);
	// 34 (100010)
	task.adjacentActiveBit(34);
	// -12 (∞11110100)
	task.adjacentActiveBit(-12);
	// 7 (111)
	task.adjacentActiveBit(7);
	// 21 (00010101)
	task.adjacentActiveBit(21);
}

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist
// Rust Program 
// Check if a number has two adjacent active bits
fn main()
{
	// Test Cases
	// 12 (1100)
	adjacent_active_bit(12);
	// 34 (100010)
	adjacent_active_bit(34);
	// -12 (∞11110100)
	adjacent_active_bit(-12);
	// 7 (111)
	adjacent_active_bit(7);
	// 21 (00010101)
	adjacent_active_bit(21);
}
fn adjacent_active_bit(num: i32)
{
	// Display given number
	print!("\n Number : {}", num);
	// Shift the given number by one on left side and perform bitwise & operation
	if num < 0 || (num & (num >> 1)) > 0
	{
		// If result are greater than zero
		// Or num less than zero
		print!("\n Adjacent active bit exist\n");
	}
	else
	{
		print!("\n Adjacent active bit not exist\n");
	}
}

Output

 Number : 12
 Adjacent active bit exist

 Number : 34
 Adjacent active bit not exist

 Number : -12
 Adjacent active bit exist

 Number : 7
 Adjacent active bit exist

 Number : 21
 Adjacent active bit not exist

Time Complexity

The time complexity of this algorithm is constant (O(1)) because the operations involved (bitwise AND, bitwise shift, comparisons) are all performed in constant time regardless of the input number.

Last updated on by Kalkicode




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