在没有内置O(n)的情况下，从LSB到MSB读取自然数的位

Question

以自然数a为输入，在O(n(时间内很容易读取其二进制形式的位，从MSB到LSB，n是其二进制长度，只使用a for循环和初等和和和和减法。左移可以通过A+A和减去1000000…来实现

def powerOfTwo(n):
a = 1
for j in range(0,n):
a=(a+a)
return a
def bitLenFast(n):
len=0
if (n==0):
len=1
else:  
y=1
while (y<=n):
y=(y+y)
len=(len+1)
return len    
def readAsBinary(x): 
len=bitLenFast(x)        # Length of input x in bits
y=powerOfTwo((len-1))    # Reference word 1000000...
hBit=powerOfTwo(len)     # Deletes highest bit in left shift
for i in range(0, len):
if (x>=y):
bit=1
x=((x+x)-hBit)    
else:
bit=0
x=(x+x)
print(bit)    

是否有一种算法可以在O(n(时间内从LSB逐位解析到MSB，只使用while或a进行循环和基本运算(即没有逐位内置函数或运算符(？

Answer 1

应用算法以MSB到LSB的顺序查找数字的位。保持累加器A初始化为0，位置值变量B初始化为1。在每次迭代中，如果位已设置，则将B添加到A，然后通过将其添加到自身来加倍B。您还需要跟踪连续0位的数量。预先将计数器C初始化为零，如果位为0，则在每次迭代时递增计数器C，否则设置为零。

最后，你会得到一个数字，其中的位在A中反转。然后你可以输出C前导零，然后将算法应用于A，以LSB到MSB的顺序输出原始数字的位。

Answer 2

这是在JS中实现samgak的answer，使用2个对OP代码的调用(改编版本(。由于OP的代码是O(n(，并且所有添加的代码都是O(1(，因此结果也是O(n(。

因此，OP问题的答案是是。

注意：根据samgak的更新答案，更新为添加前导零

function read_low_to_high(num, out) {
const acc = { 
n: 0, // integer with bits in reverse order
p: 1, // current power-of-two
z: 0, // last run of zeroes, to prepend to result once finished
push: (bit) => {  // this is O(1)
if (bit) {
acc.n = acc.n + acc.p;
acc.z = 0;
} else {
acc.z = acc.z + 1;
}
acc.p = acc.p + acc.p;
}
};
// with n as log2(num) ... 
read_high_to_low(num, acc);     // O(n) - bits in reverse order
for (let i=0; i<acc.z; i++) {   // O(n) - prepend zeroes
out.push(0);
}
read_high_to_low(acc.n, out);   // O(n) - bits in expected order
}
function read_high_to_low(num, out) {
let po2 = 1;          // max power-of-two <= num
let binlength = 1;
while (po2 + po2 <= num) {
po2 = po2 + po2;
binlength ++;
}

const hi = po2 + po2; // min power-of-two > num
for (let i=0; i<binlength; i++) {
if (num>=po2) {
out.push(1);
num = num + num - hi;
} else {
out.push(0);
num = num + num;
}
}
}
function test(i) {
const a = i.toString(2)
.split('').map(i => i-'0');
const ra = a.slice().reverse();
const b = [];
read_high_to_low(i, b);
const rb = [];
read_low_to_high(i, rb);
console.log(i,
"high-to-low",
JSON.stringify(a), 
JSON.stringify(b),
"low-to-high",
JSON.stringify(ra),
JSON.stringify(rb)
);
}
for (let i=0; i<16; i++) test(i);

Answer 3

也许你想要这样的东西：

value = 666
while value:
next = value // 2  # integer division
bit = value - next * 2
print(bit, end = " ")
value = next
>>> 0 1 0 1 1 0 0 1 0 1

Answer 4

对于读取从最低有效位到最高有效位的数字并确定数值，存在，但对于关于运行时的有效断言，如果索引访问是恒定时间，则这是至关重要的
对于数字的数值：

值←0，重量←1
前臂数字
而0<数字
值←值+重量
数字←数字-1
重量←重量+重量