3 ms·
As with all such questions, it attempts to test (creative) thinking. Also as with (almost) all such questions, knowledge can prevent that. For this example, 1/
by Someone 14y ago
As with all such questions, it attempts to test (creative) thinking. Also as with (almost) all such questions, knowledge can prevent that.
For this example, 1/3, in binary, is 0.0101010101…
From there, writing out the long multiplication will give hints towards a solution. Untested, so likely erroneous:
uint n = 12356;
uint result = 0;
while( n > 0)
{
n >>= 2;
result += n; // cheating
}
If you do not want to cheat, write a function that computes x minus 1 using but twiddling, and add a loop.
- aristidb 14y agoThe result is off by 1. :) Not bad though!
- Retric 14y agoYea, but you can correct for that. Because it's always going to be close but low. So just1 add number to it's self twice and if that's low add 1, repeat as needed. PS: Or because there is no need for it to be fast just start with zero keep adding 1 until 3x+3 > n.
- qntm 14y agoI had the same idea. The problem is that shifting the bits to the right results in decimal points falling off the end, which is actually a big deal because they add up to something substantial (i.e. more than 1) by the end of the sum. If N = 15692343, the result should be 5230781. Using "N /= 2", you get: 0 + 3923085.75 = 3923085.75 + 980771.4375 = 4903857.1875 + 245192.859375 = 5149050.046875 + 61298.21484375 = 5210348.26171875 + 15324.5537109375 = 5225672.81542969 + 3831.13842773438 = 5229503.95385742 + 957.784606933594 = 5230461.73846436 + 239.446151733398 = 5230701.18461609 + 59.8615379333496 = 5230761.04615402 + 14.9653844833374 = 5230776.01153851 + 3.74134612083435 = 5230779.75288463 + 0.935336530208588 = 5230780.68822116 + 0.233834132552147 = 5230780.92205529 + 0.0584585331380367 = 5230780.98051382 + 0.0146146332845092 = 5230780.99512846 + 0.0036536583211273 = 5230780.99878211 + 0.000913414580281824 = 5230780.99969553 + 0.000228353645070456 = 5230780.99992388 ... which eventually reaches the correct answer for any desired degree of accuracy. But using "N >>= 2", you get: 0 + 3923085 = 3923085 + 980771 = 4903856 + 245192 = 5149048 + 61298 = 5210346 + 15324 = 5225670 + 3831 = 5229501 + 957 = 5230458 + 239 = 5230697 + 59 = 5230756 + 14 = 5230770 + 3 = 5230773 + 0 = 5230773 which is out by 8.
- tzs 14y agoThis can be fixed by keeping track of some of the spillage. Here's a solution using this approach that works for 32-bit unsigned integers: def badd(A, C): while C != 0: t = A & C A = A ^ C C = (t << 1) & 0xFFFFFFFF return A def div3(ah): qh = 0 ql = 0 al = 0 while ah != 0: al = (al >> 2) & 0x0000FFFF al = badd(al, (ah & 0x3) << 14) ah = ah >> 2 qh = badd(qh, ah) ql = badd(ql, al) if ql & 0xFFFF0000: qh = badd(qh, ql >> 16) ql = ql & 0xFFFF if ql > 0x8000: qh = badd(qh, 1) return qh