1
$\begingroup$

multiplying by 33 --> $2^5 + 2^0$ is same as (num << 5) + 1

and by 65599 as (num << 16) + (num << 6) - (num << 0)

How do you get these numbers though i.e. 16,6?? I know log can be used but Is there any other quicker way to do this?

EDITED___________________

what I need to do is create a hash function such that I have to recursively multiply with numbers like 65599 or 33... hence the shift might be a better option

$\endgroup$
  • $\begingroup$ If you want to use it in python or any other programming language, please describe your use case. The most probable outcome is that is not worth it or lamguage support is poor. $\endgroup$ – Evil Apr 23 at 22:34
1
$\begingroup$

Shifting left is the same as multiply by two.
Take number, say in your example 33, convert to binary, 100001, here 1<< 6 is the leftmost bit and 1 is rightmost bit. As you have noticed it is $2^0$.

Second example is handled manually, it is 10000000000111111, so at first you set leftmost bit, then notice that consecutive ones could be converted to 1000000 - 1.

Standard usage is to speed up multiplication by constant, so you precompute it and use in your code. It makes sense until additions, subtractions and bit shifts are cheaper on target machine than one vanilla multiplication.
Some bit twidlings are already present in compilers, other may break compilers ability to optimise more.

Such operation is good in static, compiled languages, like C. It may work on managed ones (with platform independent emulation of arithmetic operations), but makes little sense on interpreted languages like Python (unless you compile it).

$\endgroup$
  • $\begingroup$ what I need to do is create a hash function such that I have to recursively multiply with numbers like 65599 or 33... hence the shift might be a better option $\endgroup$ – ABJ Apr 25 at 16:00
1
$\begingroup$

I do not understand the piece of your question "--> 25 + 20". I will ignore that, and explain the rest.

The easiest way is to look at a number in binary.

The binary for 33 is "100001".

Reading this from left to right, the digits represent (1<<5), (1<<4), (1<<3), (1<<2), (1<<1) and (1<<0). (1<<0) = 1. The last digit always represents (1<<0), which is 1. So, 33 can be expressed as 1*(1<<5) + 0*(1<<4) + 0*(1<<3) + 0*(1<<2) + 0*(1<<1) + 1*(1<<0). Since 1*x=x, and 0*x=0, this can be simplified to 33=(1<<5) + (1<<0).

So these are all the same:

  • 33 * N
  • ((1<<5) + (1<<0)) * N
  • (1<<5)*N + (1<<0)*N
  • (N<<5) + (N<<0)
  • (M<<5) + N

You can compare this to base 10 - I'll use 135 as an example here. "<

If we multiply 135*3 (base 10), we might say "(3*1) hundred + (3*3) tens + (3*5) ones = 300 + 90 + 15 = 405.

This method can be applied for any number, and will result in additions only. For the general case, any combination of powers-of-two that can be added or subtracted, can be added or subtracted in the same way. For example, 65599 in binary is "10000000000111111". I can see a long string of ones (at the end), so I would identify the lowest 1 in the series (in this case representing 1<<0), add it on here to make a simpler number, the subtract it again later:

  • 65599 = 10000000000111111
  • = 65599 +(1<<0) - (1<<0)
  • = 65600 - (1<<0)
  • = 10000000001000000 - (1<<0)
  • = (1<<16) + (1<<6) - (1<<0)

Using addition only, you the shifts are cumulative. Since 1<<2 = (1<<1)<<1, you can follow these steps to multiply A*B:

  1. total=0
  2. Convert A to binary - e.g. convert 65599 to "10000000000111111".
  3. start at the most significant (left-most) bit (bit=binary digit) of A
  4. If the bit you are looking at is a 1, then add B to total.
  5. Regardless of what bit it is, multiply the total by 2 - a.k.a total=total<<1
  6. If the bit of A you are looking is the least significant bit, stop here - total will be your answer.
  7. Otherwise, look at the next bit (moving towards the right) of A, and go back to step 4.

This is how computers often multiply. Step 2 is unnecessary for computers, because that's how they store numbers all the time.

This is much quicker than multiplying by counting - you go around the loop one per bit, with 3-4 operations per loop - add B (if appropriate); double the total; move to the next bit, conditional-branch back if not complete. Since computers deal with set sizes (e.g. 64-bit), and the highest bit is shifted out into the "carry" flag, you can treat the carry as the check if you need to add or not. This means the above code reduces to:

  • total=0
  • do 64 times:
    • A = A<<1
    • if there was a carry from the above instruction, total=total+B
    • total=total<<1

If you're following these instructions, pad A with zeroes on the left, to 64 bits; then when you shift-left (i.e. add a bit to the right), then the left-most bit becomes the carry.

$\endgroup$
0
$\begingroup$

Fundamentally, you're just doing long multiplication, as you learnt in school except in binary, rather than decimal.

Decimal long multiplication uses the fact that, e.g., $$65599 = 6\times 10^4 + 5\times10^3 + 5\times10^2 + 9\times10^1 + 9\times10^0\,,$$ and note that everything before "$\times$" is a decimal digit $0$$9$. In decimal, multiplication by $10^k$ is just shifting left $k$ digits and padding with zeros.

The binary version is using $$\begin{align*} 65599 &= 2^{16} + 2^5 + 2^4 + 2^3 + 2^2 + 2^1\\ &= 1\times 2^{16} + 0\times2^{15} + 0\times 2^{14} + \dots\,, \end{align*}$$ where everything before "$\times$" is now a binary digit $0$$1$, which looks simpler but makes no real difference. And, in binary, multiplication by $2^k$ is just a shift.

But what you've actually done is observed that $2^5+2^4+2^3+2^1+2^0 = 2^6-1$, so $65599=2^{16}+(2^6-1)$. It's not actually essential that the things before "$\times$" are digits in the number base. You could equally do long multiplication in decimal by writing $$65599 = 6\times10^4 + 5\times10^3 + 6\times10^4 - 1\times10^0\,.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.