Như ta đã biết với a và b là 2 số nguyên a*b = a*(b-1)+a khi b>0 cách làm này cũng vẫn sẽ mất b bước thực hiện. Tượng tự ta có tính chất sau trong phép nhân a*b=a*(b/2)+a*(b/2) Từ đó: ta có thể phân tích a*b như sau: a*b = a*(b/2)+a*(b/2) khi b chẵn a*b= a*(b/2) + a*(b/2)+a khi b lẻ Với tính chất này tương tự như lũy thừa ta có thể tính a*b bằng cách tính a*(b/2) mà khong cần tính a*(b-1)+a... từ đó ta có tính a*b với độ phức tạp là O(log(n)) int bin_multiplication ( int a , int b ) { int res = 0 ; while ( b > 0 ) { if ( b % 2 == 1 ) res = res + a ; a = a + a ; b = b >> 1 ; // b=b/2 } ...