一道作业题，有关低级处理，效率，Karatsuba算法

techmagician

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(a,b) { a ^= b; b ^= a; a ^= b; }

unsigned long int karatsuba(unsigned long int a, unsigned long int b);
int main () {
    unsigned long int a, b;
    srand(time(NULL));
    
    
#ifndef TEST
    a=rand(); b=rand();
    printf("%ld*%ld=%ld\n",a,b,karatsuba(a,b));
#endif
    
#ifdef TEST
    for(int i=0; i< 1000000; i++) {
        a=rand(); b=rand();
        if(karatsuba(a,b)!=a*b) {
            fprintf(stderr,"Error: a=%ld, b=%ld\n",a,b);
            exit(-1);
        }
    }
    
#endif
}

unsigned long int karatsuba(unsigned long int a, unsigned long int b) {
    int i, n, N;
    unsigned long int x0, y0;
    unsigned long int z0, z1, z2;
    if(a<b) SWAP(a,b);
    if(b==0) return 0;
    for(n=-1, i = 1; i <= b; i<<=1, n++);  /* not optimal */
    for(N=n; i <= a; i<<=1, N++);
    y0=b&((1<<n)-1);
    x0=a&((1<<N)-1);
    z2=1<<(N-n);
    z1=karatsuba(z2,y0)+x0;
    z0=karatsuba(x0,y0);
    return (z2<<(2*n))+(z1<<n)+z0;
}

                                                                                                                                Explainwhat specific adjustments were made to the algorithm inorder to improve the efficiency.



                                                                                                Write an efficient function to replace the for loops marked as “notoptimal”. Hint: you can use some assembler instructions (keyword asm), some build-incompiler functions (dependent on your compiler), or the operators &, |, << and >>
                               
                       
               
                               
                       
               


题目大致意思是说这段代码用karatsuba算法在算两个数乘积，但是用了low level的处理，让解释一下它的高效在哪.
谁能解释一下那个karatsuba函数里的代码是在干些什么啊？顺便，如何改进/* not optimal */ 的地方？