Rebol3 Code Examplex


Gosper's hack

Generate the next combination with the same number of set bits.

Rebol [
    title: "Rosetta code: Gosper's hack"
    file:  %Gosper's_hack.r3
    url:   https://rosettacode.org/wiki/Gosper%27s_hack
]

gospers-hack: function [
    "Given a bitmask, returns the next integer with the same number of set bits"
    n [integer!]
][
    c: n and negate n                 ;; lowest set bit
    r: n + c                          ;; clear the lowest run of set bits and set the next bit
    r or (((n xor r) / c) >> 2)       ;; restore the trailing set bits in the lowest positions
]

foreach n [1 3 7 15][
    prin ajoin [as-red pad n -2 ": "] ;; print starting value
    loop 10 [                         ;; print next 10 values in sequence
        n: gospers-hack n
        prin pad n 4   
    ]
    prin LF
]

Output:

 1: 2   4   8   16  32  64  128 256 512 1024
 3: 5   6   9   10  12  17  18  20  24  33  
 7: 11  13  14  19  21  22  25  26  28  35  
15: 23  27  29  30  39  43  45  46  51  53