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
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