t******e
发帖数: 1293 | 1 google搜了半天，也没有找到什么有用的信息。
应该搜什么关键字？或者提供几个link参考一下
sudoku solver bitwise operation algorithm |
|
g*********s
发帖数: 1782 | 2 【 以下文字转载自 Programming 讨论区 】
发信人: gandjmitbbs (Nothing), 信区: Programming
标 题: 问个bitwise实现加法的问题
发信站: BBS 未名空间站 (Thu Feb 3 01:35:27 2011, 美东)
unsigned bit_add(unsigned int x, unsigned int y) {
unsigned int carry = x & y;
unsigned int result = x ^ y;
while ( carry != 0 ) {
unsigned int shifted_carry = carry << 1;
carry = result & shifted_carry;
result ^= shifted_carry;
}
return result;
}
没想明白正确性。另外如果扩展到int怎么改？ |
|
j****e
发帖数: 140 | 3 I want to get 2^x. x <32. which would be faster, to lookup a table or to use
bitwise shift operator < |
|
r*****t
发帖数: 286 | 4 ☆─────────────────────────────────────☆
yaj (好玩) 于 (Wed Feb 28 10:33:35 2007) 提到:
long value;
...
value &= 0xFFFF;
编译总是出错：error: invalid operands of types `
function type>' and `long int' to binary `operator<<'
请高手指点。
☆─────────────────────────────────────☆
soar (无意) 于 (Wed Feb 28 10:46:53 2007) 提到:
I don't think the error message points to the bitwise OR line.
Which compiler are you using?
☆─────────────────────────────────────☆
yaj (好玩) 于 (Wed Feb 28 11:03: |
|
t*******r
发帖数: 22634 | 5 我觉得我现在大概明白了。
题目里的那句 “put smallest non-negative integer that does not
appear at left/below in the same column/row”，对于最小的能满足
那句话的矩阵，就是：
0 1
1 0
而上面这个矩阵，实际上就是基本 XOR 算子。
从这个矩阵开始，可以递归构建更大的满足条件的矩阵（也可以看前面彩图）。
a a + rows(a)
a + rows(a) a
而这个递归构建的过程，实际上就是从基本 XOR 算子出发，构建
bitwise-XOR 算子的过程。
因此，从这个角度看，“递归构建” vs “bitwise-XOR 算子构建”，
其实是同一个东西的两个投射。所以那个 bitwise-XOR 算子并不是
巧合。从某个角度看，bitwise-XOR 算子是自带递归的算子
（属于“自带干粮的五毛”算子哈哈）。
俺前面犯的最最主要的错误，是混淆了基本 XOR 算子，和 bitwise-XOR
算子的区别。这两者不等价。 |
|
t*******r
发帖数: 22634 | 6 我觉得 XOR 算子特性的深层原因，brainstorm 一下，可能跟下面几个有关：
（1）XOR 算子和 AND 算子是 abelian group (commutative group)
算子。在这个 ring 里面，XOR 算子相当于算术里的加法。
（2）bitwise（包括 bitwise-XOR 和 bitwise-AND），是无进位运算。
无进位运算在 recursive 构造的时候，能利用空隙里数值小的数字？
（3）综合上面两点之后，其实最最最最重要的，就是：Caylay Table
就是 99 表有木有！！！当然是 99 表的抽象代数版。。。
所以。。。其实俺没想到 XOR 算子的原因，看来是因为俺小时候 99 表
背得不熟，小学老师不够狠。。。plus 她一定 99 表背得滚瓜烂熟！！
// 哈哈，我 run 了，勿追杀，谢谢。。。 |
|
t*******r
发帖数: 22634 | 7 属实。
更准确一些的说法是：bitwise 算子的 Cayley table 没有进位。
Cayley table 本身其实可以装任何算子，也不限于对自然数的操作。
我上面贴的 Cayley table，准确的说，是 bitwise-XOR 对于非负
整数的 Cayley table。是 Cayley table 的一个特例。
所以，99 乘法表实际上也真的是 Cayley table 的另一个特例。
当然，数学狂人可能会思考，比如创建类似 bitwise-XOR 的算子，
但改成对 directed-graph 的操作而不是对自然数的操作，同时把
Cayley Table 里面的数字统统改成人神俱愤的 directed-graph
符号。。。对于这种情况，我只能说，给此类狂人毫不犹豫地扎上
一针，然后果断呼叫救护车走 carpool lane 送精神病院！！
// 哈哈， 俺 super fast run 了，请勿追杀，谢谢。。。
位， |
|
发帖数: 1 | 8 https://www.wsj.com/articles/most-bitcoin-trading-faked-by-unregulated-
exchanges-study-finds-11553259600?mod=hp_lista_pos2
Nearly 95% of all reported trading in bitcoin is artificially created by
unregulated exchanges, a new study concludes, raising fresh doubts about the
nascent market following a steep decline in prices over the past year.
Fraudulent trading volume has dogged cryptocurrency trading for years, but
the extent of the market manipulation has been difficult to determine.
Bitwise A... 阅读全帖 |
|
z*****n
发帖数: 7639 | 9 I think even in embedded microcontrollers, T2>T1, because I have NEVER
seen bitwise comparison instruction in any microcontroller.
So, in general case of bitwise comparison of a bitwise-accessable
system, it should be done in this way:
REG(a).x -> R0 ; load bit x of Register a to the first general register R0
REG(b).y -> R1 ; load bit y of Register b to the 2nd general register R1
CMP R0 R1 |
|
y****e
发帖数: 28 | 10
I believe the original problem should be restricted to a variable that
takes the same space of an integer of the machine. Then you can do the
integer bitwise operation on these two integer variables to swap the values.
From an efficiency point of view, the bitwise operation is a waste of time
as nowadays the memory is cheap.
If we want to think that the variables are plain structures, then we can use
char* to point at the beginning of the data and a loop to go through all
bytes to do exchange. ... 阅读全帖 |
|
h**k
发帖数: 3368 | 11 << 和 >> 怎么说啊？
left bitwise shift and right bitwise shift ? |
|
z*****j
发帖数: 6 | 12 1) char * ptr = “Hello”;
sizeof(ptr) = ?
a. 1
b. 4
c. 5
d. 6
2) char obj[10][20][30];
sizeof(obj) = ?
a. 6000
b. 600
c. 60
d. 1
3) char c = 127; c = c + 10;
Which of the following is true?
a. c > 0
b. c = 0
c c < 0
d .c >= 0
4) double a = 5/10*2.0;
a = ?
a. 0
b. 0.25
c. 1
d. 0.05
5) int a = 2|1; //Bitwise OR operation
a = ?
a. 0
b. 1
c. 2
d. 3
6) int a = 3^1; //Bitwise XOR operation
a = ?
a. 0
b. 1
c. 2
d. 3
7) #include
int main()
{
int a = 5;
{int a = 6;cout<
return 0;
}
Wha |
|
c*****t
发帖数: 13 | 13 本人CS硕士名校非牛人,一年前去了一家中型软件公司做SD,不喜欢,刚刚跳去一家小HF.面试
的过程好像西游记一样,路途遥遥,艰险不断,怪物层出不穷,自己的本领也日渐增长,2年来承蒙
版上各路豪杰照顾分享,今日也算有个结果;特此拿出小弟所见所闻共勉,纪念找工作的艰辛,愿
大家早日心想试成,取到真经!
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview..... 阅读全帖 |
|
G******i
发帖数: 5226 | 14 ☆─────────────────────────────────────☆
currant (葡萄干) 于 駡 提到:
/***********************
小测验
***********************/
首先来个小测验,看你能看懂多少
1.array,list,BST,Hashtable,queue,stack,suffix tree,collection...
2.BFS,DFS,DP,D&C,Greedy,Dijkstra,tree traversal,recursion,quick
sort...
3.A,F,G,L,M,O,T,Y...
4.OOP,GC,Polymorphism,interface,abstract class,singleton...
5.bar raiser,white board programming,lunch interview...
如果以上任何概念不能熟练给出详细解答,请在往下面看之后抓紧复习1.数据结构(这个如果一
个没看懂可以按后退关窗口了)2.算法3.公司背景4.面向对象编程5.on... 阅读全帖 |
|
b***p
发帖数: 700 | 15 这个是python solution, worst case 是O(n^2). 比普通的Greedy Solution, 有两个
改进
1. 计算bit map of word, and AND operation to check if there is common char
2. 遍历是从最长的word开始
还有一个可以改进的地方是，利用元音字母，用word_len+vowel 作key，减少不必要
的compare
class DiffWordsMaxLenProduct:
def __init__(self):
# dict: word -> word char bit map
self.dict_word_bit = {}
# dict: word_len -> [word1, word2, word3...]
self.dict_word_len = {}
#
# compute the bit map of word char
#
def bit_word(self... 阅读全帖 |
|
t*******r
发帖数: 22634 | 16 我觉得不严格的形象表述那个属性（形象联系 XOR 和 < 号），
就是看那张彩色的 Cayley Table 的图。
bitwise-XOR 对于自然数序列的 Caley Table 实际上是基本 XOR 矩阵
0 1
1 0
逐次在不同的位 bits 上递归叠加。（上面有人提到过这个）。
（其实这个就是 bitwise-XOR 的定义）。
（另外由于这个叠加不会出现进位，所以这个叠加跟加法也是一回事）。
而比较大小的 < 号，其实也是从最高位（最高递归层）到最低位（最低递归层）
的逐次比较。
这样从那张图上递归地看：
（1）最高位比该数的最高位小的数，在长边的排列组合都会出现。
（2）最高位和该数一样的。大家统统一起剥掉最高位，然后递归到（1）。
所以不严格的概念表示，比该数小的那些数都会出现。
彩图在这里：
'^
L |
|
t*******r
发帖数: 22634 | 17 我觉得这个就是 bitwise-XOR 算子的内在属性。。。所以这个算子很牛叉
。。。其实我一直就知道这个算子很牛叉 N 年了，可惜 N 年了都没搞清楚
为啥这个 bitwise-XOR 算子这么牛叉。。。
说句大实话，搞清一个抽象代数的简单概念，对于俺这种弱智的，也不是
一件很容易的事。。。所以说，背 99 表，做 Kumon，差不多就可以了，
数学上要背的东西太多了。。。当然，上数学竞赛的，可能要另说，那个对
熟练度要求还是不低的，俺不想误导别人。当然当然，智商 250 以上的，
我想字典里没有“熟练度”这个词。。。// run |
|
L*****e
发帖数: 8347 | 18 来自主题: Programming版 - 座席优化 这个和我昨天想的差不多。我想的是：
建一个哈希表，以20个站为key（其实19个就够，每人会在终点站买票），value是the
list of tickets which have not been sold at this (key) station.
初始时，20个key map的list都含有所有1000张票。
接到一个请求时，以请求的起点到终点之间的所有站为key查哈希表，如果任何一个的
list为空，那么说明这个请求的票卖完了，买票失败。
如果所有站对应的list都不为空，那么表示这个请求一定有票。而且这所有站中最短的
那个list的head就是最优解的票。（这点是因为这个算法保证了最碎片的票在list里总
是排在最前面，而最短的list的head才能保证所有请求中的经过站都有这个座位的票）。
现在票找到了，要把这张票从请求经过站的lists中remove掉。从所有list的头开始去
找这张票很慢。所有再给每个list里的票弄个哈希表，key为座位号，value为座位在
list里的地址，并且初建list时建double list。于是只要知道要remove掉那个座位，
就可... 阅读全帖 |
|
发帖数: 1 | 19
=====================
C++ 工程实践(4)：二进制兼容性
原创 2011年03月09日 10:46:00 标签：c++ /library /interface /mfc /class /编译
器 22578
陈硕 (giantchen_AT_gmail)
Blog.csdn.net/Solstice
本文主要讨论 Linux x86/x86-64 平台，偶尔会举 Windows 作为反面教材。
C/C++ 的二进制兼容性 (binary compatibility) 有多重含义，本文主要在“头文件和
库文件分别升级，可执行文件是否受影响”这个意义下讨论，我称之为 library （主
要是 shared library，即动态链接库）的 ABI (application binary interface)。至
于编译器与操作系统的 ABI 留给下一篇谈 C++ 标准与实践的文章。
什么是二进制兼容性
在解释这个定义之前，先看看 Unix/C 语言的一个历史问题：open() 的 flags 参数的
取值。open(2) 函数的原型是
int open(cons... 阅读全帖 |
|
h**********g
发帖数: 3962 | 20 一下是图灵官网的描述。我觉得他在密码学方面的贡献是很重要的一部分。
Yao spent a year as a Professor in the Computer Science Division of the
University of California, Berkeley, and subsequently returned to Stanford as
a full Professor in 1982. During the early 1980’s, Yao produced a number
of papers which had a lasting impact on the foundations of cryptography,
computer security, computational complexity and randomized computation. This
work was significant not only for results obtained, but also for the
introduction of problems,... 阅读全帖 |
|
r******7
发帖数: 58 | 21 下面是本人近日在Bloomberg电话面试中被问到的题目及我自己的答案。面试后我问
考官我答得如何。他说因为面试是用同一套题目，所以不能告诉我哪题答对。这样说来
，这些题目可能对大家都有用。我贴一下向本版回馈。因为我的专业是EE，对这些编程
问题也没有把握。希望大家指出我回答中的错误。多谢。
注：题目以数字排序。以字母排序的是我的回答及注解。
Asked Questions
1. How to divide a number by 8 without using division?
a) Use bitwise shift >>3
2. What is register in C?
a) Register variables are stored in the registers in CPUs. Other
variables are stored in memory chips. Thus, register is faster.
3. The return of the sizeof functi |
|
h***g
发帖数: 337 | 22 ☆─────────────────────────────────────☆
robot007 (007) 于 (Sun Oct 29 22:05:46 2006) 提到:
下面是本人近日在Bloomberg电话面试中被问到的题目及我自己的答案。面试后我问
考官我答得如何。他说因为面试是用同一套题目，所以不能告诉我哪题答对。这样说来
，这些题目可能对大家都有用。我贴一下向本版回馈。因为我的专业是EE，对这些编程
问题也没有把握。希望大家指出我回答中的错误。多谢。
注：题目以数字排序。以字母排序的是我的回答及注解。
Asked Questions
1. How to divide a number by 8 without using division?
a) Use bitwise shift >>3
2. What is register in C?
a) Register variables are stored in the registers in CPUs. Other
variables are |
|
g*******y
发帖数: 1930 | 23 来自主题: JobHunting版 - 一道面试题 网上看来的：
一堆数，其中一些数出现了一次，一些数出现了两次，只有一个数出现了三次
找出那个出现了3次的数
hash方法很trivial就不说了。
如果用bitwise operator，怎么高效的做？除了XOR，是不是还得用点别的办法？ |
|
a*****e
发帖数: 51 | 24 来自主题: JobHunting版 - 一道面试题 (1) Sorting, time: O(nlogn), space: O(1)
(2) Hashing, time: O(n), space: O(n)
(3) Bitwise operation, How can you use XOR, since after XORing every
elements, both those elements which occur 1 time and the one occurring 3
times will be left indistinguishable? |
|
c***z
发帖数: 6348 | 25 本科计算机，博士离散数学。主要优势集中在算法，反正看大家的面试题算法一类的还
算有想法。C语言还算可以。Bitwise operation常用，因此比较自信。brain teaser算
是个人爱好，还有点自信。但是其余的工作经历，实习，domain knowledge一概没有。
也面试了几次，凡是问到实践层面的我就傻眼。人家都说我有potential但是人家就是要有经验的。大家说我是不是干脆别考虑软工了？
其他的路早就堵死了，faculty因为学校差，老板人缘差，本人文章更差，不要想了；
工业届凡是跟专业有关的都要security clearance。我想做炸弹的都没这么变态的吧？
当初真是瞎了眼。好吧，自己不用功是主要原因。要是发了一堆文章，就不来这抱怨啦。 |
|
m*****f
发帖数: 1243 | 26 soduku不应该涉及到matrix, 用bitwise operation做是最佳答案
最后一题我觉得应该用hashtable + B+tree吧. 自动分配的时候总往size最小的一个子树分配，一个高度为电话号码长度+1的十叉树 |
|
g*******y
发帖数: 1930 | 27 赞！
bless lz～
linkedlist那题，没有说空间限制的话，先想到hash很正常！
sodoku那题用bitwise做比较方便。
最后一个用trie比较好 |
|
R***r
发帖数: 120 | 28 soduku用bitwise怎么做啊？大牛们可否稍微讲解一下？ |
|
|
g*******y
发帖数: 1930 | 30 见过只让用bitwise的题，还没见过说不让用的，这有什么意思呢...
ps，A+A+..+A这类的方法比较慢
用个分冶的思路，A*B = A*(B/2)+A*(B-B/2)
只考虑绝对值:
int mul(int A, int B){
if(B==0) return 0;
if(B==1) return A;
int result= mul(A,B/2);
return result + result + (B%2)?A:0;
} |
|
i**********b
发帖数: 77 | 31 从一到面试题里想到的问题。
0x80000001 >> 1 == 0xC0000000;
0x80000001 << 1 == 2;
C++ 测试过的。
第一个是把left most的bit copy 了一下。跟我理解的一样。
第二个呢？很奇怪呀。如果把right most的bit copy 一下应该得到3呀。 怎么是2呢？ |
|
d***d
发帖数: 24 | 32 Default is to fill 0, not copy
Since the number is signed integer, when you right shift, the sign bit gets
copied. |
|
g*******y
发帖数: 1930 | 33 你知道为什么右移要copy最高位吗？先把这个理解一下 |
|
i**********b
发帖数: 77 | 34 how to fill with 1 during left shift then?
gets |
|
s*****w
发帖数: 1527 | 35 1. Given inputs X, Y, Z and operations | and & (meaning bitwise OR and AND,
respectively)
What is output equal to in
output = (X & Y) | (X & Z) | (Y & Z)
2. why const char* can be both a character and a string declaration ? |
|
l*******r
发帖数: 511 | 36 是怎么做的？google了一大堆也不能理解怎么检查input是不是valid。。 |
|
|
|
|
|
|
|
|
m******9
发帖数: 968 | 44 这个题目在编程之美上有, 最快的方法是查表, O(1)的复杂度.
不过面试的时候, 还是写个bitwise+loop的方法吧 |
|
t**g
发帖数: 1164 | 45 比如-1
假设8个bit
应该是0减去1
所以变成
0000 0000 -> 1111 1111
么？？ |
|
|
m*****g
发帖数: 226 | 47 那个bitwise的也有点扯淡了
除非经常搞那些的
看样子是接近底层和系统方面的吧
fb |
|
b****r
发帖数: 1272 | 48 sum method will suffer overflow issues and may no tbe what interviewers are
looking for
for 1 missing number, one can use bitwise (2^n-1) searching - count # of 0s
and 1s at each digit
for >1 missing numbers, binary search is one of the approaches |
|
i**********b
发帖数: 77 | 49 1）为什么 new 出来的object 不能用free。 malloc出来的object不能用delete。
我说了constructor，destructor 的原因.他们还问有没有其他原因。假设不涉及资源
分配问题。
2）SQL alias是用来干嘛的。不会，乱答的
3)为什么assign operator 不能自己assign 给自己。没打上来
4）算法题： 一个array里找唯一一个duplicated integer
5）abstract class, pure virtual function. why use them
两个老印，一男一女。女的极度tough. 我还在一边说一边想呢。她居然challenge我说
"now what?!" 算法题我给了两个解法。一个sort，binary search，另一个bitwise
XOR。那个男的让我用个例子go through 一下。我马上就快说完了。那女的居然说“we
are running out of time".其实才不到45分钟。而且我就差一句了。 剩下的15分钟
我可以问问题。真没礼貌。 不知道bloomberg的人 |
|
i**********b
发帖数: 77 | 50 哦。array length n,
the range of the integers in the array is n-1.
所以只有一个duplicated.
比如：
array: 1, 2, 3, 2, 4
len = 5;
range 1 - 4;
第一步：
sum = 1 ^ 2 ^ 3 ^ 4
第二步：
用sum 去 XOR array中每个一个元素
只有 2 被XOR了两次。 其他1,3,4都被XOR了一次。
bitwise XOR 有个特点。 x ^ x = 0 （一次XOR)
x ^ x ^ x = x (两次XOR)
所以上面两个步骤之后最后 sum = 2
这个题貌似很经典吧。呵呵 |
|
