C
Sorry for the bulky code, I am still a noob. The idea is to grab the first piece of bits from n such that k #include <stdio.h>
unsigned int rightMostBit(unsigned int n){
unsigned int bitmask=0x1 << 31;
int position=31;
while((bitmask & n)==0 && position>=0){
position-=1;
bitmask = bitmask>>1;
}
return position;
}
unsigned int extractBits(unsigned int n, unsigned int start, unsigned int end){
unsigned int unitMask=0x1;
unsigned int mask=unitMask << start;
for(int i=start;i<end;i++){
mask= (mask | (mask << 1));
}
return ((mask & n) >> start);
}
void longDivision(unsigned int n, unsigned int k)
{
unsigned int q=0;
unsigned int head=rightMostBit(n);
int tail=head;
unsigned int r=extractBits(n,tail,head);
while(k>r && tail>=0){
tail-=1;
r=extractBits(n,tail,head);
}
while(pointMask>0) //scan all bits of n
{
if(k<= r){ //If k less than r, we can do division
r-= k ; //subtraction
q=q << 1; //make space
q = q | 0x1; //add a 1 to quotient
}else{
q=q << 1; //make space
q= q | 0x0; //k > r, so add 0 to quotient
}
//stick r with next bit from n
pointMask=pointMask >> 1;
if(pointMask!=0){
if((pointMask & n)){
r=((r << 1) | 1);
}else{
r=((r << 1) | 0);
}
}
}
printf("quotient: %d, remainder: %d \n",q,r);
}
