相关疑难解决方法(0)

此问题来自2011 Codesprint(http://csfall11.interviewstreet.com/):

计算机科学的基础之一是知道数字如何以2的补码表示.想象一下,使用32位写下A和B之间的所有数字,包括2的补码表示.你会写下多少1？输入:第一行包含测试用例数T(<1000).每个下一个T行包含两个整数A和B.输出:输出T行,一行对应于每个测试用例.约束:-2 ^ 31 <= A <= B <= 2 ^ 31 - 1

样品输入:3 -2 0 -3 4 -1 4样品输出:63 99 37

说明:对于第一种情况,-2包含31 1后跟0,-1包含32 1和0包含0 1.因此,总是63.对于第二种情况,答案是31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

我意识到你可以使用-X中的1的数量等于(-X)= X-1的补码中的0的数量以加速搜索的事实.该解决方案声称有一个O(log X)递归关系用于生成答案但我不明白.解决方案代码可以在这里查看:https://gist.github.com/1285119

如果有人能解释这种关系是如何产生的,我将不胜感激!

关于位操作,我之前有一个面试问题.该公司是一家知名的GPU公司.我在汇编语言方面的背景很少(尽管是计算机架构的博士生,但很奇怪),正如这个叙述所表明的那样,我把它搞砸了.问题很简单:

"编写一个快速代码,用于计算32位寄存器中1的数量."

现在我正在研究手臂组装.所以我很自然地再次重新讨论这个问题,并通过研究ISA来提出这个代码.

对于你那里的专家来说,这是对的吗？有更快的方法吗？作为初学者,我自然认为这是不完整的."xx"中的AND指令感觉多余,但没有其他方法可以在ARM中移位寄存器...

R1将包含末尾的位数,而R2是包含我们想要计数的位的寄存器.r6只是一个虚拟寄存器.评论附在()中

    MOV   R1, #0                (initialize R1 and R6 to zero)
    MOV   R6, #0        
xx: AND   R6, R6, R2, LSR #1    (Right shift by 1, right most bit is in carry flag)
    ADDCS R1, #1                (Add #1 to R1 if carry  flag is set)
    CMP R2, #0                  (update the status flags if R2 == 0 or not)
    BEQ xx                      (branch back to xx until R2==0)

我的数据库(oracle 11g)中很少有blob被复制,使用UTL_RAW.BIT_XOR对blob执行XOR操作.之后我想计算二进制字符串中的设置位数,所以写了上面的代码.

在一个小实验中,我想看看生成的十六进制和整数值是什么,并编写了这个程序.

SQL> declare
2
3 vblob1 blob;
4
5 BEGIN
6
7 select leftiriscode INTO vblob1 FROM irisdata WHERE irisid=1;
8
9 dbms_output.put_line(rawtohex(vblob1));
10
11
12 dbms_output.put_line(UTL_RAW.CAST_TO_binary_integer(vblob1));
13
14
15 END;
16 /

输出:HEXVALUE:

0F0008020003030D030C1D1C3C383C330A3311373724764C54496C0A6B029B84840547A341BBA83D
BB5FB9DE4CDE5EFE96E1FC6169438344D604681D409F9F9F3BC07EE0C4E0C033A23B37791F59F84F
F94E4F664E3072B0229DA09D9F0F1FC600C2E380D6988C198B39517D157E7D66FE675237673D3D28
3A016C01411003343C76740F710F0F4F8FE976E1E882C186D316A63C0C7D7D7D7D397F016101B043
0176C37E767C7E0C7D010C8302C2D3E4F2ACE42F8D3F3F367A46F54285434ABB61BDB53CBF6C7CC0
F4C1C3F349B3F7BEB30E4A0CFE1C85180DC338C2C1C6E7A5CE3104303178724CCC5F451F573F3B24
7F24052000202003291F130F1B0E070C0E0D0F0E0F0B0B07070F1E1B330F27073F3F272E2F2F6F7B
2F2E1F2E4F7EFF7EDF3EBF253F3D2F39BF3D7F7FFED72FF39FE7773DBE9DBFBB3FE7A76E777DF55C
5F5F7ADF7FBD7F6AFE7B7D1FBE7F7F7DD7F63FBFBF2D3B7F7F5F2F7F3D7F7D3B3F3B7FFF4D676F7F
5D9FAD7DD17F7F6F6F0B6F7F3F767F1779364737370F7D3F5F377F2F3D3F7F1F2FE7709FB7BCB77B
0B77CF1DF5BF1F7F3D3E4E7F197F571F7D7E3F7F7F7D7F6F4F75FF6F7ECE2FFF793EFFEDB7BDDD1F
FF3BCE3F7F3FBF3D6C7FFF7F7F4FAF7F6FFFFF8D7777BF3AE30FAEEEEBCF5FEEFEE75FFEACFFDF0F
DFFFF77FFF677F4FFF7F7F1B5F1F5F146F1F1E1B3B1F3F273303170F370E250B

INTEGER VALUE: 15

十六进制代码和生成的整数值之间存在差异,因此使用以下python代码检查实际的整数值.

print int("0F0008020003030D030C1D1C3C383C330A3311373724764C54496C0A6B029B84840547A341BBA83D
BB5FB9DE4CDE5EFE96E1FC6169438344D604681D409F9F9F3BC07EE0C4E0C033A23B37791F59F84F
F94E4F664E3072B0229DA09D9F0F1FC600C2E380D6988C198B39517D157E7D66FE675237673D3D28
3A016C01411003343C76740F710F0F4F8FE976E1E882C186D316A63C0C7D7D7D7D397F016101B043
0176C37E767C7E0C7D010C8302C2D3E4F2ACE42F8D3F3F367A46F54285434ABB61BDB53CBF6C7CC0
F4C1C3F349B3F7BEB30E4A0CFE1C85180DC338C2C1C6E7A5CE3104303178724CCC5F451F573F3B24
7F24052000202003291F130F1B0E070C0E0D0F0E0F0B0B07070F1E1B330F27073F3F272E2F2F6F7B
2F2E1F2E4F7EFF7EDF3EBF253F3D2F39BF3D7F7FFED72FF39FE7773DBE9DBFBB3FE7A76E777DF55C
5F5F7ADF7FBD7F6AFE7B7D1FBE7F7F7DD7F63FBFBF2D3B7F7F5F2F7F3D7F7D3B3F3B7FFF4D676F7F
5D9FAD7DD17F7F6F6F0B6F7F3F767F1779364737370F7D3F5F377F2F3D3F7F1F2FE7709FB7BCB77B
0B77CF1DF5BF1F7F3D3E4E7F197F571F7D7E3F7F7F7D7F6F4F75FF6F7ECE2FFF793EFFEDB7BDDD1F
FF3BCE3F7F3FBF3D6C7FFF7F7F4FAF7F6FFFFF8D7777BF3AE30FAEEEEBCF5FEEFEE75FFEACFFDF0F
DFFFF77FFF677F4FFF7F7F1B5F1F5F146F1F1E1B3B1F3F273303170F370E250B",16)

回答:

611951595100708231079693644541095422704525056339295086455197024065285448917042457
942011979060274412229909425184116963447100932992139876977824261789243946528467423
887840013630358158845039770703659333212332565531927875442166643379024991542726916
563271158141698128396823655639931773363878078933197184072343959630467756337300811
165816534945075483141582643531294791665590339000206551162697220540050652439977992
246472159627917169957822698172925680112854091876671868161705785698942483896808137
210721991100755736178634253569843464062494863175653771387230991126430841565373390
924951878267929443498220727531299945275045612499928105876210478958806304156695438
684335624641395635997624911334453040399012259638042898470872203581555352191122920
004010193837249388365999010692555403377045768493630826307316376698443166439386014
145858084176544890282148970436631175577000673079418699845203671050174181808397880
048734270748095682582556024378558289251964544327507321930196203199459115159756564 …

这个问题的灵感来自于我昨天的工作.

假设我们有N个输入,评估为真或假,哪种输入的X是真的最有效的方法是什么？

注意事项:

1. 输入不在数组中,因此如果将它们转换为数组,请考虑任何管理费用.
2. "效率最高"我指的是最佳平均情况(尽管我也希望看到最佳和最差情况统计数据).

这是我昨天遇到的两种方法.

1)将变量视为电路的布尔输入,并使用K-map减少它们

起初我认为这将是最有效的手段,因为它遵循电路逻辑,但我肯定有第二个想法.随着输入数量的增加,比较次数呈指数增长

2 inputs:
   1 of 2: if(1 OR 2)
   2 of 2: if(1 AND 2)

3 inputs:
   1 of 3: if(1 OR 2 OR 3)
   2 of 3: if((1 AND 2) OR (1 AND 3) OR (2 AND 3))
   3 of 3: if(1 AND 2 AND 3)

4 inputs:
   1 of 4: if(1 OR 2 OR 3 OR 4)
   2 of 4: if((1 AND 2) OR (1 AND 3) OR (1 AND 4) …

我正在寻找在512或更多字节的大缓冲区上popcount的最快方法.我可以保证任何所需的对齐,缓冲区大小总是2的幂.缓冲区对应于块分配,因此通常位是全部设置,没有设置,或者大多数设置有利于缓冲区的"左",偶尔出洞.

我考虑过的一些解决方案是:

• GCC的 __builtin_popcount
• Bitslice popcount_24words
• 计数位设置,Brian Kernighan的方式

我对最快的解决方案感兴趣,它必须适用于属于core2或更近的32位x86芯片组.SSE和SIMD非常感兴趣.我将在以下四核CPU上进行测试:

matt@stanley:~/anacrolix/public/stackoverflow$ cat /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz
stepping        : 11
cpu MHz         : 1600.000
cache size      : 4096 KB
physical id     : 0
siblings        : 4
core id         : 0
cpu cores       : 4
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : …

任务是仅使用按位运算符实现位计数逻辑.我的工作正常,但我想知道是否有人可以提出更优雅的方法.

只允许使用Bitwise操作.没有"if","for"等

int x = 4;

printf("%d\n", x & 0x1);
printf("%d\n", (x >> 1) & 0x1);
printf("%d\n", (x >> 2) & 0x1);
printf("%d\n", (x >> 3) & 0x1);

谢谢.

可能重复:
计算32位整数中设置位数的最佳算法？

我想找出一个数字的二进制表示中有多少1个.我有2个逻辑.

1.   int count =0;
   int no = 4;
   
   while(no!=0){
       int d = no%2;
       if(d==1)
           count++;
       no = no/2;
       str = str+ d;
   }
   

   Run Code Online (Sandbox Code Playgroud)

2. 现在第二个逻辑是用1,2,4,8,32迭代地继续屏蔽数字,并检查结果是否为1,2,4,8 ......我没有确定该循环应该结束的条件.

可能重复:
创建具有特定位数的多个数字

我正在尝试编写一些代码,通过将位移位来将每个可能的数字组合放在一个数组中.

例如,我想找到数组应该包含的3位(最大数字可以是6)的所有可能组合:

000111
001011
001101
001110
010011
010101
010110
011001
011010
011100
100011

等等...

根据我的解释,当最后一个位置为1时,我们将数字移1(x >> 1)并在开始时加1.但是,我不确定如何编写其余的代码.我用C来写这个.

另外 - 据我所知,这是一个colex序列,但是,如果有另一个序列可以给我相同的最终结果(具有约束为N的k位的所有可能组合的数组),我都是耳朵. .

我有一个256位值的数组.该数组是巨大的(数百万条记录),但它很少被修改,它适合内存.对于给定的256位数,我想查找是否存在至少N位相等的记录.例如,10000和01111的0位相等,1000和1001的3位相等.总是N> 128,或者更确切地说N> 140.我不需要找到特定的数字,我只需要查找列表中是否存在这样的数字.

是否有一种数据结构或某种索引可以某种方式加速搜索？

假设我有一个整数I,并希望以二进制形式得到1的计数.

我目前正在使用以下代码.

Number(i.toString(2).split("").sort().join("")).toString().length;

有更快的方法吗？我正在考虑使用按位运算符.有什么想法吗？

注意: i在32位限制范围内.