2021-05-24

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 in binary representation as $N.

#!/usr/bin/tclsh

proc nexthigher {x} {
    set next 0

    if {$x} {
        set rightOne [expr $x & -$x]
        set nextHigherOneBit [expr $x + $rightOne]
        set rightOnesPattern [expr $x ^ $nextHigherOneBit]
        set rightOnesPattern [expr $rightOnesPattern / $rightOne]
        set rightOnesPattern [expr $rightOnesPattern >> 2]
        set next [expr $nextHigherOneBit | $rightOnesPattern]
    }

    return $next
}

if {$argc >= 1} {
    set number [lindex $argv 0]
} elseif {$argc == 0} {
    exit    
}

if {$number < 0} {
    exit
}

puts "Output: [nexthigher $number]"