确定两个整数之间的字典距离

Question

假设我们有lexicographicaly整数3,5,6,9,10,12 or 0011,0101,0110,1001,1010,1100每个都有两个位设置.

我想要的是在说3和5尽可能少的操作之间找到距离(它们之间有多少字典排列,而不进行实际排列).

距离表如下

3->5  = 1 or 0011->0101 = 0001
3->6  = 2 or 0011->0110 = 0010
3->9  = 3 or 0011->1001 = 0011
3->10 = 4 or 0011->1010 = 0100
3->12 = 5 or 0011->1100 = 0101

因此函数f(3,5)将返回1;

该函数将始终采用相同汉明权重(相同的设定位数)的参数.

不应该使用任何数组.

任何想法都会很棒.

编辑

忘记提及,对于任何设定的比特大小(汉明重量),我将始终使用第一个词典排列(base)作为第一个参数.

例如

hamming weight 1 base = 1
hamming weight 2 base = 3
hamming weight 3 base = 7
...

编辑2

解决方案适用于任何汉明重量,抱歉我不够具体.

Answer 1

具有数
x = 2 ^{k ₁} + 2 ^{k ₂} + ... + 2 ^{k _m}
其中k ₁ <k ₂ <... <k _m
可以声称数字x的位置在按字典顺序排列的所有数字序列中相同的汉明权重是
lex_order(X)= C(K ₁,1)+ C(K ₂,2)+ ... + C(K _米,米)
其中,C(N,M)= N!/米! /(纳米)!如果m> n,则为0或0

例:

3 = 2 ⁰ + 2 ¹
lex_order(3)= C(0,1)+ C(1,2)= 0 + 0 = 0

5 = 2 ⁰ + 2 ²
lex_order(5)= C(0,1)+ C(2,2)= 0 + 1 = 1

6 = 2 ¹ + 2 ²
lex_order(6)= C(1,1)+ C(2,2)= 1 + 1 = 2

9 = 2 ⁰ + 2 ³
lex_order(9)= C(0,1)+ C(3,2)= 0 + 3 = 3