m**********d 发帖数: 40 | 1 最近onsite的时候刚拿到一道面试题,what is a computational fast way to divide
an integer by 7.
有大神有思路么?
求个解答算法或者代码? |
l******s 发帖数: 3045 | 2 循环(除数*8+7)去比较被除数
divide
【在 m**********d 的大作中提到】 : 最近onsite的时候刚拿到一道面试题,what is a computational fast way to divide : an integer by 7. : 有大神有思路么? : 求个解答算法或者代码?
|
n*******s 发帖数: 17267 | |
l******s 发帖数: 3045 | 4 private static int divideBy7(int num){
if (num == int.MinValue) return -divideBy7(int.MaxValue);
if (num < 0) return -divideBy7(-num);
int result = 0;
while (num >= 7){
int subResult = 1, div = 7;
while (((div << 3) | 7) > 0 && num >= ((div << 3) | 7)){
div = (div << 3) | 7;
subResult = subResult << 3 | 1;
}
while ((div << 1) > 0 && num >= (div << 1)){
div <<= 1; subResult <<= 1;
}
num -= div; result += subResult;
}
return result;
} |
g****7 发帖数: 8 | 5 int div7(int num)
{
int Q, R, sum;
// got this from post #4
if ( num < 0 )
return (-div7(-num));
R = num;
sum = 0;
while (R & 0xFFF8 )
{
Q = R >> 3;
sum += Q;
R = R & 0x7;
R = R + Q;
}
if ( R == 7 )
sum++;
return sum;
} |
g****7 发帖数: 8 | 6 // one fewer calculation
int div7(int num)
{
int Q, R, sum;
// got this from post #4
if ( num < 0 )
return (-div7(-num));
R = num;
sum = 0;
Q = R >> 3;
while (Q)
{
sum += Q;
R = R & 0x7;
R = R + Q;
Q = R >> 3;
}
if ( R == 7 )
sum++;
return sum;
} |
s********g 发帖数: 92 | 7 按位置1后乘7(右移三位再减自己),看是不是比被除数大,大的话该位置回零
int div7(int num) {
if (num < 0)
return -div7(-num);
int H = num >> 2;
int bits = 0;
while(H > 0){
H >>= 1;
bits ++;
}
int res = 0;
for( ; bits >= 0 ; bits--) {
int mask = 1 << bits;
res = res | mask;
int a = (res << 3) - res;
if (a == num)
return res;
else if (a > num)
res = res ^ mask;
}
return res;
} |