Peter’s blog ✴ Week 114 ✴ 24 May 2021

THE WEEKLY CHALLENGE
Next highest

The Perl Camel

Task 2

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.

I am sorry that the 'Try it' feature is currently working very slowly or not at all owing to some issue with my web hosting provider.

Try it 

Try running the script with any input:



example: 12345

Script


#!/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;
}

14 lines of code
Completed after the closing date and not submitted to GitHub

Output from script


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)

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain