Skip to main content

Find next bigger number with same number of set bits

Given an integer number our goal is to find next largest number by using of same number of set bits. See the following example.

 Example 1
Given num =  120 (001111000)
Output    =  135 (010000111)
{
    Step (1) Finding the zero which is followed by one
            From left to right 
            0 0 1 1 1 1 0 0 0 <- find zero
              -
    Step  (2) Swap the zero bit to the right side one
            0 1 0 1 1 1 0 0 0 
              - -  
    Step  (3)  After swap divide the result into two selection
            One is all right side bits of current swap bits (include swap)
            And second is left side part of swap bits
            0 1 0  1 1 1 0 0 0 
            _____  ___________
              1        2
    Step (4) shift all set bits in second part to the left side
            0 1 0  1 1 1 0 0 0 
            _____  ___________
              1        2

            0 1 0   0 0 0  1 1 1
            _____  ___________
              1        2

    Final Result   
            [010000111]       
}
Example 2
Given num =  82  (1010010)

Output    =  84 (1010100)
{
    Step (1) Finding the zero which is followed by one
            From left to right 
            1 0 1 0 0 1 0 <- find zero
                    -
    Step  (2) Swap the zero bit to the right side one
             1 0 1 0 1 0 0
                     - -  
    Step  (3)  After swap divide the result into two selection
            One is all right side bits of current swap bits (include swap)
            And second is left side part of swap bits
            1 0 1 0 1 0   0 
            __________   ____
                1         2
    Step (4) Second part have no set bit 
           
    Final Result   
            [1010100]       
}

Here given code implementation process.

// C program
// Find next bigger number with same number of set bits
#include <stdio.h>

void nextHigher(int num)
{
	// Get the right most set bits
	int c = (num & -num);
	int r = num + c;
	// Calculate next Higher
	int ans = ((((r ^ num) >> 2) / c) | r);
	// Display given number
	printf("\n Given number : %d", num);
	// Display calculated result
	printf("\n Result       : %d\n", ans);
}
int main(int argc, char
	const *argv[])
{
	// Test case
	nextHigher(120);
	nextHigher(82);
	return 0;
}

Output

 Given number : 120
 Result       : 135

 Given number : 82
 Result       : 84
// Java program
// Find next bigger number with same number of set bits
public class Higher
{
	// Find next bigger number with same number of set bits
	public void nextHigher(int num)
	{
		// Get the right most set bits
		int c = (num & -num);
		int r = num + c;
		// Calculate next Higher
		int ans = ((((r ^ num) >> 2) / c) | r);
		// Display given number
		System.out.print("\n Given number : " + num);
		// Display calculated result
		System.out.print("\n Result : " + ans + "\n");
	}
	public static void main(String[] args)
	{
		Higher task = new Higher();
		// Test case
		task.nextHigher(120);
		task.nextHigher(82);
	}
}

Output

 Given number : 120
 Result : 135

 Given number : 82
 Result : 84
// Include header file
#include <iostream>
using namespace std;

// C++ program
// Find next bigger number with same number of set bits

class Higher
{
	public:
		// Find next bigger number with same number of set bits
		void nextHigher(int num)
		{
			// Get the right most set bits
			int c = (num &-num);
			int r = num + c;
			// Calculate next Higher
			int ans = ((((r ^ num) >> 2) / c) | r);
			// Display given number
			cout << "\n Given number : " << num;
			// Display calculated result
			cout << "\n Result : " << ans << "\n";
		}
};
int main()
{
	Higher task = Higher();
	// Test case
	task.nextHigher(120);
	task.nextHigher(82);
	return 0;
}

Output

 Given number : 120
 Result : 135

 Given number : 82
 Result : 84
// Include namespace system
using System;
// C# program
// Find next bigger number with same number of set bits
public class Higher
{
	// Find next bigger number with same number of set bits
	public void nextHigher(int num)
	{
		// Get the right most set bits
		int c = (num & -num);
		int r = num + c;
		// Calculate next Higher
		int ans = ((((r ^ num) >> 2) / c) | r);
		// Display given number
		Console.Write("\n Given number : " + num);
		// Display calculated result
		Console.Write("\n Result : " + ans + "\n");
	}
	public static void Main(String[] args)
	{
		Higher task = new Higher();
		// Test case
		task.nextHigher(120);
		task.nextHigher(82);
	}
}

Output

 Given number : 120
 Result : 135

 Given number : 82
 Result : 84
<?php
// Php program
// Find next bigger number with same number of set bits
class Higher
{
	// Find next bigger number with same number of set bits
	public	function nextHigher($num)
	{
		// Get the right most set bits
		$c = ($num & -$num);
		$r = $num + $c;
		// Calculate next Higher
		$ans = ((intval((($r ^ $num) >> 2) / $c)) | $r);
		// Display given number
		echo "\n Given number : ". $num;
		// Display calculated result
		echo "\n Result : ". $ans ."\n";
	}
}

function main()
{
	$task = new Higher();
	$task->nextHigher(120);
	$task->nextHigher(82);
}
main();

Output

 Given number : 120
 Result : 135

 Given number : 82
 Result : 84
// Node Js program
// Find next bigger number with same number of set bits
class Higher
{
	// Find next bigger number with same number of set bits
	nextHigher(num)
	{
		// Get the right most set bits
		var c = (num & -num);
		var r = num + c;
		// Calculate next Higher
		var ans = ((parseInt(((r ^ num) >> 2) / c)) | r);
		// Display given number
		process.stdout.write("\n Given number : " + num);
		// Display calculated result
		process.stdout.write("\n Result : " + ans + "\n");
	}
}

function main()
{
	var task = new Higher();
	// Test case
	task.nextHigher(120);
	task.nextHigher(82);
}
main();

Output

 Given number : 120
 Result : 135

 Given number : 82
 Result : 84
#  Python 3 program
#  Find next bigger number with same number of set bits
class Higher :
	#  Find next bigger number with same number of set bits
	def nextHigher(self, num) :
		#  Get the right most set bits
		c = (num & -num)
		r = num + c
		#  Calculate next Higher
		ans = ((int(((r ^ num) >> 2) / c)) | r)
		#  Display given number
		print("\n Given number : ", num, end = "")
		#  Display calculated result
		print("\n Result : ", ans )
	

def main() :
	task = Higher()
	#  Test case
	task.nextHigher(120)
	task.nextHigher(82)

if __name__ == "__main__": main()

Output

 Given number :  120
 Result :  135

 Given number :  82
 Result :  84
#  Ruby program
#  Find next bigger number with same number of set bits
class Higher 
	#  Find next bigger number with same number of set bits
	def nextHigher(num) 
		#  Get the right most set bits
		c = (num & -num)
		r = num + c
		#  Calculate next Higher
		ans = ((((r ^ num) >> 2) / c) | r)
		#  Display given number
		print("\n Given number : ", num)
		#  Display calculated result
		print("\n Result : ", ans ,"\n")
	end

end

def main() 
	task = Higher.new()
	#  Test case
	task.nextHigher(120)
	task.nextHigher(82)
end

main()

Output

 Given number : 120
 Result : 135

 Given number : 82
 Result : 84
// Scala program
// Find next bigger number with same number of set bits
class Higher
{
	// Find next bigger number with same number of set bits
	def nextHigher(num: Int): Unit = {
		// Get the right most set bits
		var c: Int = (num & -num);
		var r: Int = num + c;
		// Calculate next Higher
		var ans: Int = (((((r ^ num) >> 2) / c).toInt) | r);
		// Display given number
		print("\n Given number : " + num);
		// Display calculated result
		print("\n Result : " + ans + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Higher = new Higher();
		// Test case
		task.nextHigher(120);
		task.nextHigher(82);
	}
}

Output

 Given number : 120
 Result : 135

 Given number : 82
 Result : 84
// Swift 4 program
// Find next bigger number with same number of set bits
class Higher
{
	// Find next bigger number with same number of set bits
	func nextHigher(_ num: Int)
	{
		// Get the right most set bits
		let c: Int = (num & -num);
		let r: Int = num + c;
		// Calculate next Higher
		let ans: Int = ((((r ^ num) >> 2) / c) | r);
		// Display given number
		print("\n Given number : ", num, terminator: "");
		// Display calculated result
		print("\n Result : ", ans );
	}
}
func main()
{
	let task: Higher = Higher();
	// Test case
	task.nextHigher(120);
	task.nextHigher(82);
}
main();

Output

 Given number :  120
 Result :  135

 Given number :  82
 Result :  84
// Kotlin program
// Find next bigger number with same number of set bits
class Higher
{
	// Find next bigger number with same number of set bits
	fun nextHigher(num: Int): Unit
	{
		// Get the right most set bits
		var c: Int = (num and - num);
		var r: Int = num + c;
		// Calculate next Higher
		var ans: Int = ((((r xor num) shr 2) / c) or r);
		// Display given number
		print("\n Given number : " + num);
		// Display calculated result
		print("\n Result : " + ans + "\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Higher = Higher();
	// Test case
	task.nextHigher(120);
	task.nextHigher(82);
}

Output

 Given number : 120
 Result : 135

 Given number : 82
 Result : 84
// Rust program
// Find next bigger number with same number of set bits
fn main()
{
	// Test case
	next_higher(120);
	next_higher(82);
}
fn next_higher(num: i32)
{
	// Get the right most set bits
	let  c: i32 = num & -num;
	let  r: i32 = num + c;
	// Calculate next Higher
	let  ans: i32 = (((r ^ num) >> 2) / c) | r;
	// Display given number
	print!("\n Given number : {}", num);
	// Display calculated result
	print!("\n Result : {}\n", ans);
}

Output

 Given number : 120
 Result : 135

 Given number : 82
 Result : 84




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