0

So I was reading a question on SO and I don't understand the code of the answer it has. It is doing some bit wise operation but i don't know how that works and what is actually going on within the while loop and the need of mod at b2 = (b2*b2) % m

        b2 = b                         
        res = 1                        
         while e:                       
            if e & 1:                  
                res = (res * b2) % m   
            b2 = (b2*b2) % m        
            e >>= 1

Can anyone help me to understand it ?

This is the question

Dutta
  • 326
  • 1
  • 3
  • 10

1 Answers1

2

It is a bitwise AND operation. In bitwise binary operations, the two numbers in their binary form are processed by their corresponding bits. So 1 is only one bit. It will be compared to last bit of a number. So a&1 will return 1 if last bit of 1 is 1 and zero otherwise. So the if block will be executed accordingly eg 12 AND 1
1 1 0 0
0 0 0 1
_________
0 0 0 0

Tojra
  • 673
  • 5
  • 20
  • What do you mean by **two numbers in their binary form are processed by their corresponding bits** ? Any why its making its mod of m twice ? – Dutta Mar 31 '19 at 16:00
  • 2
    I mean just write the numbers in their binary form,one below the other(same way we write to add two numbers) such that their last bit matches. So then perform AND on each pair of bits. So for 1101 AND 1 you will write 1101 AND 0001 . It gives 0001. this way – Tojra Mar 31 '19 at 16:05