超难VS基础： 如何快速判断10的倍数？
二进制 十进制
1010： 10
10100 20
...... ......
问题：
给一个二进制串，如何判断是否为10的倍数？
进一步：
给一个二进制串，如果已经知道是10的倍数，如何快速计算除以10后的结果？
[解决办法]
x/10可以转化为
(x*0xCCCCCCCD)> > 35
而
x*0xCCCCCCCD由于非常规律，也可以转化为一些加法和移位运算。
[解决办法]
up
[解决办法]
我只知道可以取模，一般编译器都支持
[解决办法]
“x/10可以转化为
(x*0xCCCCCCCD)> > 35
而
x*0xCCCCCCCD由于非常规律，也可以转化为一些加法和移位运算。”
能否给解释一下，看不懂：）
[解决办法]
x*0xCCCCCCCD
x稍微大点就溢出了.
没有想到通用的好方法,求余吧.
[解决办法]
把字符串转化成数字，然后对10取模，即可判断
只需扫描一次字符串就可以
[解决办法]
The last digit is 0, it is ok.
[解决办法]
原理:
32数a0.....a31;(0 <=ai <2)
看出4进制 b0......b15;(0 <=bi <4)
10的倍数 现在先求5的倍数, 2的倍数比较简单.
5的4进制为11;
所以5的倍数 的4进制数 有下特性:
|(b0+b2+....+b14) - (b1+b3+.....+b15)|为5的倍数.
这个数在0-24(3*8)之间比较容易判断
测试代码的函数
int check(unsigned int x)
{
int i;
if(x&0x01)
return 0;
int a=x> > 1;
int b = 0;
int c = 0;
int d;
for(i=0;i <8;i++)
{
b += (a> > (i*4))&0x03;
}
for(i=0;i <8;i++)
{
c += (a> > (i*4+2))&0x03;
}
if(b> c)
{
d = b-c;
}
else
{
d = c-b;
}
for(i=0;i <=3*8;i+=5)
{
if(d==i)
return 1;
}
return 0;
}
[解决办法]
...不能按后两位逻辑与吗？？
[解决办法]
告诉你们。你们都错了
[解决办法]
参考单片机编程
[解决办法]
先判断整除2：看最后一位是否为0
再判断整除5：由2的各次方幂mod5分别为：1，2，4，3，1，2，4，3 .......
所以，分别数4个序列中1的个数，设为a,b,c,d 然后判断 if( a-c+2(b-d)== 0)
至于如何求a,b,c,d，以a(mod5=1)为例，令y=x and 0001000100010001...
于是转换为求二进制数y中1的个数，一种方法为：
int func(unsigned int n)
{
int count=0;
while(n> 0)
{
n&=(n-1);
count++;
}
return count;
}
[解决办法]
楼上的方法不错
2的倍数除以5的余数正好构成一个周期数
然后把所有的字符从低到高按照周期，找出剩余的几位
[解决办法]
mark
[解决办法]
改进了一下testDivisibility999，在我的电脑上似乎更快
inline const BOOL testDivisibility999_zyl( const UINT32 u32Num )
{ /* by zyl910@sina.com, 2007-08-09 */
__asm
{
mov eax, u32Num;
imul eax, 0xCFBE65FD7;// 999 的乘法逆元素
cmp eax, 4299266;// (2^32-1)/999
mov eax, 0;
setbe al;
}
}
CPU: Intel Pentium 4, 1515 MHz (15 x 101), L2 Cache 256KB
内存: 128MB, DDR 266MHz
操作系统: Windows XP sp2
编译器: VC++ 6.0 sp5
请按任意键继续. . .
统计固定的随机 16777216 个数(SEED=12345678)中可被 10 整除的数：
直接取余法：count = 1677964,time is: 61328 ms
查表法：count = 1677964,time is: 2328 ms
汇编优化-v07：count = 1677964,time is: 312 ms
汇编优化-v08：count = 1677964,time is: 204 ms
汇编优化-v09：count = 1677964,time is: 187 ms
位段计算法：count = 1677964,time is: 859 ms
位段移位综合：count = 1799059,time is: 344 ms
移位计算法：count = 1677964,time is: 297 ms
汇编优化-lbc2：count = 1677964,time is: 328 ms
汇编优化-lbc3：count = 1677964,time is: 313 ms
汇编优化-zyl：count = 1677964,time is: 187 ms
汇编优化-zyl1：count = 1677964,time is: 141 ms
汇编优化-zyl2：count = 1677964,time is: 187 ms
汇编优化-zyl3：count = 1677964,time is: 172 ms
再统计该组随机数中可被 999 整除的数：
直接取余法：count = 16911,time is: 438 ms
汇编优化：count = 16911,time is: 172 ms
汇编优化-zyl：count = 16911,time is: 125 ms
我修改了一下测试代码，在开始测试前等待按键
这样在运行测试时可以将该进程的优先级设为“实时”
[解决办法]
mark
[解决办法]
只发现
1010+后边为0
与1111+后边为0的数为10的倍数
后边就不知道怎么判断了
[解决办法]
请测试：testDivisibility10_zyl_lbc(4294967290)，返回值为“0”！
究其原因，是测试程序有缺陷，因为 RAND_MAX = 0x7FFF！
请大家将随机测试数据的生成代码改成“pTestData[i] = ( rand() < < 17 ) | rand();”即可。
[解决办法]
建议版主加精！！！
