Exploration of bit operations to compute the next permutation with constant number of ones

001-next-bits-permutation.md

Next Permutation

... code to view each step of the "next permutation" bit manipulation algorithm ...

002-next_perm.py

import math
import numpy as np

n = 20

def bin(v):
	return np.binary_repr(v, width = n)

v = 0b1001110000
t = (v | (v - 1)) + 1
w = t | ((((t & -t) // (v & -v)) >> 1) - 1)

# print("=" * 55)
print(f"v                     = {bin(v)}")
print(f"v - 1                 = {bin(v - 1)}")
print()
print(f"v's least significant 0 bits set to 1")
print(f"v | (v - 1)           = {bin(v | (v - 1))}")
print()
print(f"t = (v | (v - 1)) + 1 = {bin((v | (v - 1)) + 1)}")
# print()
# print(f" 6 = {bin(6)}")
# print(f"-6 = {bin(-6)}")
print()
print(f" v     = {bin(v)}")
print(f"-v     = {bin(-v)}")
print(f"v & -v = {bin(v & -v)}")
print(f" t     = {bin(t)}")
print(f"-t     = {bin(-t)}")
print(f"t & -t = {bin(t & -t)}")
print()
print(f"t & -t                      = {bin(t & -t)}")
print(f"v & -v                      = {bin(v & -v)}")
print(f"(t & -t) // (v & -v)        = {bin((t & -t) // (v & -v))}")
print(f"((t & -t) // (v & -v)) >> 1 = {bin(((t & -t) // (v & -v)) >> 1)}")
print()
print(f"((t & -t) // (v & -v)) >> 1             = {bin(((t & -t) // (v & -v)) >> 1)}")
print(f"(((t & -t) // (v & -v)) >> 1) - 1       = {bin((((t & -t) // (v & -v)) >> 1) - 1)}")
print(f"t | ((((t & -t) // (v & -v)) >> 1) - 1) = {bin(t | ((((t & -t) // (v & -v)) >> 1) - 1))}")
print()
print(f"in  = {bin(v)}")
print(f"out = {bin(w)}")

003-output.txt

v                     = 00000000001001110000
v - 1                 = 00000000001001101111

v's least significant 0 bits set to 1
v | (v - 1)           = 00000000001001111111

t = (v | (v - 1)) + 1 = 00000000001010000000

 v     = 00000000001001110000
-v     = 11111111110110010000
v & -v = 00000000000000010000
 t     = 00000000001010000000
-t     = 11111111110110000000
t & -t = 00000000000010000000

t & -t                      = 00000000000010000000
v & -v                      = 00000000000000010000
(t & -t) // (v & -v)        = 00000000000000001000
((t & -t) // (v & -v)) >> 1 = 00000000000000000100

((t & -t) // (v & -v)) >> 1             = 00000000000000000100
(((t & -t) // (v & -v)) >> 1) - 1       = 00000000000000000011
t | ((((t & -t) // (v & -v)) >> 1) - 1) = 00000000001010000011

in  = 00000000001001110000
out = 00000000001010000011