Task — Higher integer set bits

You are given a positive integer $N.

Write a script to find the next higher integer having the same number of 1 bits as $N.

Examples

Example 1
Input: $N = 3
Output: 5
Binary representation of $N is 011. There are two 1 bits. 
   So the next higher integer is 5 having the same the 
   number of 1 bits i.e. 101.

Example 2
Input: $N = 12
Output: 17
Binary representation of $N is 1100. There are two 1 
   bits. So the next higher integer is 17 having the same 
   number of 1 bits i.e. 10001.

Analysis

It would be possible to come up with an algorithm to do this, similar to that in task 1. However, I found that it's quite fast, for most values, to repeatedly increment and count bits until the wanted count is found.

Even with, say 2**18 - containing only 1 1-bit - it takes only a few seconds to come up with the answer, ie 2**19.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-05-24
use utf8;     # Week 114 - task 2 - Higher integer set bits
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

higher_integer_set_bits(3);
higher_integer_set_bits(5);
higher_integer_set_bits(99);
higher_integer_set_bits(920);
higher_integer_set_bits(20210524);
higher_integer_set_bits(31415926535);
higher_integer_set_bits(2 ** 18);

sub higher_integer_set_bits {
    
    my ($n, $bits, $next);
    
    # initialise
    $n = $_[0];
    
    # count bits and find next
    $bits = count_bits($n);
    $next = $n + 1;
    $next ++ until count_bits($next) == $bits;
    
    say qq[\nInput:  ] . sprintf('%d = %b', $n, $n) . qq[ ($bits 1-bits)];
    say qq[Output: ] . sprintf('%d = %b', $next, $next) . qq[ ($bits 1-bits)];
}

sub count_bits {
    
    my ($n, $count);
    
    $n = $_[0];
    $count = 0;
    $count += (2 ** $_ & $n) != 0 ? 1 : 0 for 0 .. 63;
    return $count;
}

last updated 2026-04-01 — 14 lines of code

Output

Input:  3 = 11 (2 1-bits)
Output: 5 = 101 (2 1-bits)

Input:  5 = 101 (2 1-bits)
Output: 6 = 110 (2 1-bits)

Input:  99 = 1100011 (4 1-bits)
Output: 101 = 1100101 (4 1-bits)

Input:  920 = 1110011000 (5 1-bits)
Output: 929 = 1110100001 (5 1-bits)

Input:  20210524 = 1001101000110001101011100 (12 1-bits)
Output: 20210531 = 1001101000110001101100011 (12 1-bits)

Input:  31415926535 = 11101010000100010001111111100000111 
   (18 1-bits)
Output: 31415926539 = 11101010000100010001111111100001011 
   (18 1-bits)

Input:  262144 = 1000000000000000000 (1 1-bits)
Output: 524288 = 10000000000000000000 (1 1-bits)