| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 305 人关注过本帖
标题:刚看到一个题目,觉有很有趣
只看楼主 加入收藏
风吹过b
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:307
帖 子:4687
专家分:29121
注 册:2008-10-15
结帖率:100%
收藏
 问题点数:0 回复次数:14 
刚看到一个题目,觉有很有趣
刚看到一个题目,觉有很有趣,有点适合新手。

一个整数在计算机里是按二进制的形式保存的,现在要求统计这个整数的二进制形式里包含多少个1。编写段程序进行统计。
如,12345678 包含 12 个 1 。

-------------
为了方便调用和测试运算速度,额外规定如下:
使用 函数 形式定义程序,输入参数为一个整数,返回结果也是一个整数

如:
程序代码:
Public Function CountOne(cs As Long) As Long
Dim k As Long
Dim j As Long
    k = 1
    j = 0
Do While k < cs
    If (k And cs) > 0 Then
        j = j + 1
    End If
    k = k * 2
Loop
CountOne = j
End Function


我想到二种方法来统计,这是最快的一种。看看大家还想得到更多的办法吗?
这个函数过几天我注释讲解一下给新手看。
搜索更多相关主题的帖子: 统计 函数 Long 形式 整数 
2021-09-11 23:13
kings12333
Rank: 2
等 级:论坛游民
帖 子:22
专家分:34
注 册:2012-11-29
收藏
得分:0 
回复 楼主 风吹过b
版主,能不能讲解一下关于VB 数组方面的知识或教材
2021-09-12 20:10
diycai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:8
帖 子:36
专家分:178
注 册:2021-5-18
收藏
得分:0 
想比你这个快10倍很容易,空间换时间。
建立0~255数字中1数量对应的表。
将long直接转换为byte型数组,直接查找表累加就是结果。
2021-09-12 20:52
风吹过b
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:307
帖 子:4687
专家分:29121
注 册:2008-10-15
收藏
得分:0 
以下是引用kings12333在2021-9-12 20:10:49的发言:

版主,能不能讲解一下关于VB 数组方面的知识或教材


这个内容真是一下子不知从哪里总结,基础知识其实百度能搜索到很多,多看看就能了解。
数组的难点其实是高级应用。

VB的数组,在内存的结构里是有数组类型说明符和数组大小,然后数组首地址,就是最小下标的那个地址。我们一般直接能操作的就是这个首地址。
VB没有指针,那么VB有些时候需要使用到指针类型的操作怎么办,除下函数调用时的取地址外,很多时候只能借助数组来进行。
这里被借助的数组,只是 byte 类型的数组了。
如,有些API要求传入一个缓冲区指针,然后API没有返回值,而是在这个缓冲区里写数据,这个缓冲区在VB6里就是先定义一个长度的BYTE数组,然后传递数组的首地址过去,
调用API后,API收到的数组首地址,在这里地址向后开始写内容。这个方法就是利VB数组保存在内存里的连续性,相当于在申请的一块内存,当做缓冲区, 又可以使用下标访问每一个地址。

当然VB数组数据转基本类型数据都必须使用复制内存的方法来转换,而没有强制类型转换,这是最不方便,掌握了方法也是很简单。
还有一个,VB不支持ANSI字符串,需要使用ANSI字符串时,就必须使用 BYTE数组来保存。

数组方面的运用,一个是看文章,还有一个就是自己多练习,用到了才会掌握,光看不练是没有用的。

授人于鱼,不如授人于渔
早已停用QQ了
2021-09-12 20:55
风吹过b
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:307
帖 子:4687
专家分:29121
注 册:2008-10-15
收藏
得分:0 
回复 3楼 diycai
你试试看

程序代码:
Public Function CountOne3(cs As Long) As Long

Dim k As Long
Dim j As Long
Dim f(0 To 3) As Byte

CopyMemory f(0), cs, 4          '复制到byte数组中

For k = 0 To 3                  '针对每个byte进行判断
    Select Case f(k)
    Case 0
    Case 1, 2, 4, 8, 16, 32, 64, 128
        j = j + 1
    Case 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129, 130, 132, 136, 144, 160, 192
        j = j + 2
    Case 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 131, 133, 134, 137, 138, 140, 145, 146, 148, 152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224
        j = j + 3
    Case 15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240
        j = j + 4
    Case 31, 47, 55, 59, 61, 62, 79, 87, 91, 93, 94, 103, 107, 109, 110, 115, 117, 118, 121, 122, 124, 143, 151, 155, 157, 158, 167, 171, 173, 174, 179, 181, 182, 185, 186, 188, 199, 203, 205, 206, 211, 213, 214, 217, 218, 220, 227, 229, 230, 233, 234, 236, 241, 242, 244, 248
        j = j + 5
    Case 63, 95, 111, 119, 123, 125, 126, 159, 175, 183, 187, 189, 190, 207, 215, 219, 221, 222, 231, 235, 237, 238, 243, 245, 246, 249, 250, 252
        j = j + 6
    Case 127, 191, 223, 239, 247, 251, 253, 254
        j = j + 7
    Case 255
        j = j + 8
    End Select
Next k
CountOne3 = j
End Function


运行是编译后运行,为什么写到1亿次呢,实在是方法一用时太短。
运行时间结果
循环调用10000000次,计时间
方法一用时:0.28125(我一楼的代码)
方法二用时:19.70313(转八进制,然后比较字符串的速度)
方法三用时:12.48438(这楼的代码)


[此贴子已经被作者于2021-9-12 21:49编辑过]


授人于鱼,不如授人于渔
早已停用QQ了
2021-09-12 21:11
风吹过b
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:307
帖 子:4687
专家分:29121
注 册:2008-10-15
收藏
得分:0 
程序代码:
Public Function countone4(cs As Long) As Long

Dim oneb(255) As Long

oneb(0) = 0
oneb(1) = 1
oneb(2) = 1
oneb(3) = 2
oneb(4) = 1
oneb(5) = 2
oneb(6) = 2
oneb(7) = 3
oneb(8) = 1
oneb(9) = 2
oneb(10) = 2
oneb(11) = 3
oneb(12) = 2
oneb(13) = 3
oneb(14) = 3
oneb(15) = 4
oneb(16) = 1
oneb(17) = 2
oneb(18) = 2
oneb(19) = 3
oneb(20) = 2
oneb(21) = 3
oneb(22) = 3
oneb(23) = 4
oneb(24) = 2
oneb(25) = 3
oneb(26) = 3
oneb(27) = 4
oneb(28) = 3
oneb(29) = 4
oneb(30) = 4
oneb(31) = 5
oneb(32) = 1
oneb(33) = 2
oneb(34) = 2
oneb(35) = 3
oneb(36) = 2
oneb(37) = 3
oneb(38) = 3
oneb(39) = 4
oneb(40) = 2
oneb(41) = 3
oneb(42) = 3
oneb(43) = 4
oneb(44) = 3
oneb(45) = 4
oneb(46) = 4
oneb(47) = 5
oneb(48) = 2
oneb(49) = 3
oneb(50) = 3
oneb(51) = 4
oneb(52) = 3
oneb(53) = 4
oneb(54) = 4
oneb(55) = 5
oneb(56) = 3
oneb(57) = 4
oneb(58) = 4
oneb(59) = 5
oneb(60) = 4
oneb(61) = 5
oneb(62) = 5
oneb(63) = 6
oneb(64) = 1
oneb(65) = 2
oneb(66) = 2
oneb(67) = 3
oneb(68) = 2
oneb(69) = 3
oneb(70) = 3
oneb(71) = 4
oneb(72) = 2
oneb(73) = 3
oneb(74) = 3
oneb(75) = 4
oneb(76) = 3
oneb(77) = 4
oneb(78) = 4
oneb(79) = 5
oneb(80) = 2
oneb(81) = 3
oneb(82) = 3
oneb(83) = 4
oneb(84) = 3
oneb(85) = 4
oneb(86) = 4
oneb(87) = 5
oneb(88) = 3
oneb(89) = 4
oneb(90) = 4
oneb(91) = 5
oneb(92) = 4
oneb(93) = 5
oneb(94) = 5
oneb(95) = 6
oneb(96) = 2
oneb(97) = 3
oneb(98) = 3
oneb(99) = 4
oneb(100) = 3
oneb(101) = 4
oneb(102) = 4
oneb(103) = 5
oneb(104) = 3
oneb(105) = 4
oneb(106) = 4
oneb(107) = 5
oneb(108) = 4
oneb(109) = 5
oneb(110) = 5
oneb(111) = 6
oneb(112) = 3
oneb(113) = 4
oneb(114) = 4
oneb(115) = 5
oneb(116) = 4
oneb(117) = 5
oneb(118) = 5
oneb(119) = 6
oneb(120) = 4
oneb(121) = 5
oneb(122) = 5
oneb(123) = 6
oneb(124) = 5
oneb(125) = 6
oneb(126) = 6
oneb(127) = 7
oneb(128) = 1
oneb(129) = 2
oneb(130) = 2
oneb(131) = 3
oneb(132) = 2
oneb(133) = 3
oneb(134) = 3
oneb(135) = 4
oneb(136) = 2
oneb(137) = 3
oneb(138) = 3
oneb(139) = 4
oneb(140) = 3
oneb(141) = 4
oneb(142) = 4
oneb(143) = 5
oneb(144) = 2
oneb(145) = 3
oneb(146) = 3
oneb(147) = 4
oneb(148) = 3
oneb(149) = 4
oneb(150) = 4
oneb(151) = 5
oneb(152) = 3
oneb(153) = 4
oneb(154) = 4
oneb(155) = 5
oneb(156) = 4
oneb(157) = 5
oneb(158) = 5
oneb(159) = 6
oneb(160) = 2
oneb(161) = 3
oneb(162) = 3
oneb(163) = 4
oneb(164) = 3
oneb(165) = 4
oneb(166) = 4
oneb(167) = 5
oneb(168) = 3
oneb(169) = 4
oneb(170) = 4
oneb(171) = 5
oneb(172) = 4
oneb(173) = 5
oneb(174) = 5
oneb(175) = 6
oneb(176) = 3
oneb(177) = 4
oneb(178) = 4
oneb(179) = 5
oneb(180) = 4
oneb(181) = 5
oneb(182) = 5
oneb(183) = 6
oneb(184) = 4
oneb(185) = 5
oneb(186) = 5
oneb(187) = 6
oneb(188) = 5
oneb(189) = 6
oneb(190) = 6
oneb(191) = 7
oneb(192) = 2
oneb(193) = 3
oneb(194) = 3
oneb(195) = 4
oneb(196) = 3
oneb(197) = 4
oneb(198) = 4
oneb(199) = 5
oneb(200) = 3
oneb(201) = 4
oneb(202) = 4
oneb(203) = 5
oneb(204) = 4
oneb(205) = 5
oneb(206) = 5
oneb(207) = 6
oneb(208) = 3
oneb(209) = 4
oneb(210) = 4
oneb(211) = 5
oneb(212) = 4
oneb(213) = 5
oneb(214) = 5
oneb(215) = 6
oneb(216) = 4
oneb(217) = 5
oneb(218) = 5
oneb(219) = 6
oneb(220) = 5
oneb(221) = 6
oneb(222) = 6
oneb(223) = 7
oneb(224) = 3
oneb(225) = 4
oneb(226) = 4
oneb(227) = 5
oneb(228) = 4
oneb(229) = 5
oneb(230) = 5
oneb(231) = 6
oneb(232) = 4
oneb(233) = 5
oneb(234) = 5
oneb(235) = 6
oneb(236) = 5
oneb(237) = 6
oneb(238) = 6
oneb(239) = 7
oneb(240) = 4
oneb(241) = 5
oneb(242) = 5
oneb(243) = 6
oneb(244) = 5
oneb(245) = 6
oneb(246) = 6
oneb(247) = 7
oneb(248) = 5
oneb(249) = 6
oneb(250) = 6
oneb(251) = 7
oneb(252) = 6
oneb(253) = 7
oneb(254) = 7
oneb(255) = 8

Dim k As Long
Dim j As Long
Dim f(0 To 3) As Byte

CopyMemory f(0), cs, 4          '复制到byte数组中

For k = 0 To 3
    j = j + oneb(f(k))
Next k

countone4 = j

End Function



循环调用10000000次,计时间
方法一用时:0.3046875
方法二用时:17.00781
方法三用时:11.6875
方法四用时:5.765625 (本楼代码)



[此贴子已经被作者于2021-9-12 21:59编辑过]


授人于鱼,不如授人于渔
早已停用QQ了
2021-09-12 21:48
风吹过b
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:307
帖 子:4687
专家分:29121
注 册:2008-10-15
收藏
得分:0 
循环调用10000000次,计时间
方法一用时:0.3046875
方法四用时:2.5

稍微修改一下,把表申明了静态变量,其实这是为测试为取巧的方法。
Static oneb(255) As Long
If oneb(1) = 0 Then
    oneb(0) = 0
    oneb(1) = 1
    …………
End If

授人于鱼,不如授人于渔
早已停用QQ了
2021-09-12 22:49
风吹过b
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:307
帖 子:4687
专家分:29121
注 册:2008-10-15
收藏
得分:0 
Dim k As Long
Dim j As Long
    k = 1            '初始模板:0000 0000 0000 0000 0000 0000 0000 0001
    j = 0            '计数变量
Do While k < cs      '模板小于目标值时,说明还要继续测试
    If (k And cs) > 0 Then     '模板与目标数进行位运行AND,结果只有二种,0 或 非0 。
        j = j + 1              '非0,表示该位上为1,计数
    End If
    k = k * 2                  '模板乘2,就是把模板的1向前移1位,相当于 左移操作,按理来说,编译后优化应该是 左移操作
Loop
CountOne = j
End Function

速度分析:
    k = 1               赋值,局部变量是在堆栈里的,这是对应的汇编就是: mov 地址,立即数
    j = 0
Do While k < cs         这里生成二条汇编,cmp 和 jnc   ,本条及以下均不考虑 mov 指令了
    If (k And cs) > 0 Then   这里生成   and  和 jz
        j = j + 1      add
    End If
    k = k * 2          左移操作,SHL
Loop
不考虑mov 后,一个循环流程约需要 6条 指令。这速度怎么会不快呢。最坏情况下需要循环31次。vb 的long 是有符号,有效位只有31位。好吧,这里发现了我程序中的bug。
当然这只是最理想的状态,VB6 的编译器没这么好,如是否会优化为 SHL 指令这个不知道;还有每次运算后如 add 后,VB6 一定会加一条判断 Jo 指令。

对于 这个程序段来说,
CopyMemory f(0), cs, 4          '估计这里开销很大
For k = 0 To 3
    j = j + oneb(f(k))        这里要先mov k,然后寻址,再mov f ,再寻址mov oneb ,然后再add,指令也很少,但不知道为啥时间就会很长。只能与 CopyMemory 耗时太长有关了。
Next k
换个写法再来测试一下。

授人于鱼,不如授人于渔
早已停用QQ了
2021-09-12 23:29
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:210
帖 子:2010
专家分:11188
注 册:2014-12-6
收藏
得分:0 
有一个更有效的算法,二进制数里面有几个1,就循环几次。核心算式是cs=cs and (cs-1),例如二进制数010000000000000000,用楼主算法,需要循环16次,用这个算式就只要循环1次。
还见过一个更有效的,只需要四次运算即可,不需要循环,该算法是利用原数对几种栅格数据做与运算即可(栅格数据如10101010、01010101),具体怎么实现忘了。

能编个毛线衣吗?
2021-09-13 01:20
diycai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:8
帖 子:36
专家分:178
注 册:2021-5-18
收藏
得分:0 
用C语言测试了一下,Intel i5 1.8G的CPU,耗时如下:

循环1000万次, 测试数据 0~9999999
1楼  552ms
3楼  66ms
9楼  71ms

循环1亿次, 测试数据 0~99999999
1楼   5799ms
3楼   689ms
9楼   800ms
程序代码:
#include <stdio.h>
#include<time.h>

#define TIMES    100000000

int fun1(int n)//n必须为正数
{
    int count = 0;

    while (n)
    {
        if (n & 1)
        {
            count++;
        }
        n >>= 1;
    }

    return count;
}

int table[256];
void fun2Init()
{
    int i;
    for (i=0; i<256; i++)
    {
        table[i] = fun1(i);
    }
}

int fun2(int n)
{
    unsigned char *p;

    p = (unsigned char *)&n;
    
    return table[p[0]] + table[p[1]] + table[p[2]] + table[p[3]];
}

int fun3(int n)
{
    int count = 0;

    while (n)
    {
        n = n & (n-1);
        count++;
    }

    return count;
}

void main()
{
    int i;
    int count[3] = {0};
    clock_t t;

    t = clock();
    for (i=0; i<TIMES; i++)
    {
        count[0] += fun1(i);
    }
    t = clock() - t;
    printf("fun1 %d ms\n", t);

    fun2Init();
    t = clock();
    for (i=0; i<TIMES; i++)
    {
        count[1] += fun2(i);
    }
    t = clock() - t;
    printf("fun2 %d ms\n", t);

    t = clock();
    for (i=0; i<TIMES; i++)
    {
        count[2] += fun3(i);
    }
    t = clock() - t;
    printf("fun3 %d ms\n", t);


    if (count[0] ^ count[1])
    {
        printf("error1 %d %d\n", count[0], count[1]);
        return;
    }

    if (count[1] ^ count[2])
    {
        printf("error2 %d %d\n", count[0], count[1]);
        return;
    }
}
2021-09-13 08:19
快速回复:刚看到一个题目,觉有很有趣
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.596208 second(s), 8 queries.
Copyright©2004-2021, BCCN.NET, All Rights Reserved