This algorithm goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop. In the worst case, it will pass once per bit. An integer n has log(n) bits, hence the worst case is … Read more
This algorithm goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop. In the worst case, it will pass once per bit. An integer n has log(n) bits, hence the worst case is … Read more
Unless you’re using an ancient compiler, it can already handle this level of conversion on its own. That is to say, a modern compiler can and will implement i % 2 using a bitwise AND instruction, provided it makes sense to do so on the target CPU (which, in fairness, it usually will). In other … Read more
First remember that machine words are of fixed size. Say 4, and that your input is: +—+—+—+—+ | a | b | c | d | +—+—+—+—+ Then pushing everything one position to the left gives: +—+—+—+—+ | b | c | d | X | +—+—+—+—+ Question what to put as X? with a … Read more
Any power of 2 minus 1 is all ones: (2 N – 1 = 111….b) 2 = 2^1. 2-1 = 1 (1b) 4 = 2^2. 4-1 = 3 (11b) 8 = 2^3. 8-1 = 7 (111b) Take 8 for example. 1000 & 0111 = 0000 So that expression tests if a number is NOT a … Read more
One thing to notice about bitmasks like that is that they are always one less than a power of two. The expression 1 << n is the easiest way to get the n-th power of two. You don’t want Zero to provide a bitmask of 00000001, you want it to provide zero. So you need … Read more
(n & (n – 1)) == 0 is best. However, note that it will incorrectly return true for n=0, so if that is possible, you will want to check for it explicitly. http://www.graphics.stanford.edu/~seander/bithacks.html has a large collection of clever bit-twiddling algorithms, including this one.
Suppose Bits are numbered from LSB to MSB: BIT NUMBER 31 0 ▼ ▼ number bits 0000 0000 0000 0000 0000 0000 0001 0101 ▲ ^ ^ ▲ MSB | | LSB | | n=27 m=17 LSB – Least Significant Bit (numbered 0) MSB – Most Significant Bit (numbered 31) In the figure above, I … Read more
Use this for creating the power set of x: function power(x, y) { var r = [y || []], // an empty set/array as fallback l = 1; for (var i=0; i<x.length; l=1<<++i) // OK, l is just r[i].length, but this looks nicer 🙂 for (var j=0; j<l; j++) { r.push(r[j].slice(0)); // copy r[j].push(x[i]); } … Read more
First, a paper you should consider reading, if you want to understand floating point foibles better: “What Every Computer Scientist Should Know About Floating Point Arithmetic,” http://www.validlab.com/goldberg/paper.pdf And now to some meat. The following code is bare bones, and attempts to produce an IEEE-754 single precision float from an unsigned int in the range 0 … Read more