CODEWITHSUNDEEP
algorithmbit-manipulation
Marcos Gonzalez
Marcos Gonzalez

Reputation: 1096

Reading the bits of a natural number from LSB to MSB without built-ins in O(n)

Taking a natural number a as input, it is easy to read the bits of its binary form from MSB to LSB in O(n) time, n being its binary length, using only a for loop and elementary sums and subtractions. A left shift can be achieved by a+a and subtracting 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)

Is there an algorithm to parse a bit by bit from LSB to MSB in O(n) time, using only a while or a for loop and elementary operations (i.e. no bitwise built-in functions or operators)?

Upvotes: 0

Views: 559

Answers (4)

tucuxi
tucuxi

Reputation: 17945

This is an implementation of samgak's answer in JS, using 2 calls to (an adapted version of) OP's code. Since OP's code is O(n), and all added code is O(1), the result is also O(n).

Therefore, the answer to OP's question is yes.

NOTE: updated to add leading zeroes as per samgak's updated answer.

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);

Upvotes: 2

samgak
samgak

Reputation: 24427

Apply your algorithm to find the bits in MSB to LSB order to the number. Keep an accumulator A initialized to 0 and a place value variable B initialized to 1. At each iteration, add B to A if the bit is set and then double B by adding it to itself. You also need to keep track of the number of consecutive 0 bits. Initialize a counter C to zero beforehand and at each iteration increment it if the bit is 0 or set to zero otherwise.

At the end you will have the number with the bits reversed in A. You can then output C leading zeros and then apply the algorithm to A to output the bits of the original number in LSB to MSB order.

Upvotes: 2

greybeard
greybeard

Reputation: 2494

For reading digits from least significant to most significant and determining the numerical value, there is, but for a valid assertion about run time it would be essential if e.g. indexed access is constant time.
For digits in numerical value:

value ← 0, weight ← 1
foreach digit
  while 0 < digit
    value ← value + weight
    digit ← digit - 1
  weight ← weight + weight
 

Upvotes: 0

MBo
MBo

Reputation: 80287

Perhaps you want something like this:

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

Upvotes: 1

Related Questions