0

So I have been told that this can be done and that bitwise operations and masks can be very useful but I must be missing something in how they work.

I am trying to calculate whether a number, say x, is a multiple of y. If x is a multiple of y great end of story, otherwise I want to increase x to reach the closest multiple of y that is greater than x (so that all of x fits in the result). I have just started learning C and am having difficulty understanding some of these tasks.

Here is what I have tried but when I input numbers such as 5, 9, or 24 I get the following respectively: 0, 4, 4.

    if(x&(y-1)){ //if not 0 then multiple of y
        x = x&~(y-1) + y;
    }

Any explanations, examples of the math that is occurring behind the scenes, are greatly appreciated.

EDIT: So to clarify, I somewhat understand the shifting of bits to get whether an item is a multiple. (As was explained in a reply 10100 is a multiple of 101 as it is just shifted over). If I have the number 16, which is 10000, its complement is 01111. How would I use this complement to see if an item is a multiple of 16? Also can someone give a numerical explanation of the code given above? Showing this may help me understand why it does not work. Once I understand why it does not work I will be able to problem solve on my own I believe.

lauren
  • 11
  • 4
  • To do that you have no other choice than finding the remainder of the division. Bitwise operators can't check the remainder directly. However you can do a division with only bitwise operators. But then your question should be "how to do a division with only bitwise operators?" which was asked many times on this site – phuclv Mar 24 '15 at 05:44
  • possible duplicate of [implement division with bit wise operator](http://stackoverflow.com/questions/5284898/implement-division-with-bit-wise-operator) – phuclv Mar 24 '15 at 05:44
  • [How can I multiply and divide using only bit shifting and adding?](http://stackoverflow.com/questions/2776211/how-can-i-multiply-and-divide-using-only-bit-shifting-and-adding), [Divide two integers using only bitwise operations](http://stackoverflow.com/questions/12539877/divide-two-integers-using-only-bitwise-operations) – phuclv Mar 24 '15 at 05:45
  • I was asked to use this method in a lab and I didn't understand it then and now I am looking towards finals and need to understand it before then. The code given above is similar to what my instructor gave just generalized. I have found the multiple using mod (remainder) before but that isn't the method that was asked of me. I was also specifically asked to use a mask with the mask set to the complement of y-1. – lauren Mar 24 '15 at 14:50
  • WHAT?! let's try an easy one, addition, first: `0x1^0x1`, oh wait a sec, no carry bit, oh – Jason Hu Mar 24 '15 at 16:08

3 Answers3

1

I'm not sure why would you even think about using bit-wise operations for this? They certainly have their place but this isn't it.

A better method is to simply use something like:

unsigned multGreaterOrEqual(unsigned x, unsigned y) {
    if ((x % y) == 0)
        return x;
    return (x / y + 1) * y;
}

But to answer your added query as to how you would work out if a number is a multiple of sixteen, that can be done relatively easily. You'll notice a pattern in all the multiples below:

  0 == 0000 0000 0000 0000
 16 == 0000 0000 0001 0000
 32 == 0000 0000 0010 0000
 48 == 0000 0000 0011 0000
 64 == 0000 0000 0100 0000
 :
512 == 0000 0010 0000 0000
                      \__/
                       \
                        These bits are always zero.

So a multiple of sixteen can be detected with the expression:

(value & 0x0f) == 0

However, this will only work with powers of two, not with arbitrary divisors.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • 2
    While I agree that bitwise operations are not the obvious choice for production code, I'm guessing that it was some sort of programming assignment, an aside in a class or workplace (meant for fun), or some sort of interview question that's been blown into a scope larger than it was intended. – Edwin Buck Mar 24 '15 at 03:49
  • Yes this was presented in a lab and then an assignment. – lauren Mar 24 '15 at 14:54
  • Another use case I have come across; if your target processor doesn't have an opcode for modulos, and you need to run this operation many times. For instance an embedded 8bit AVR MCU, where you have very limited performance overhead and an optimisation like this would not be caught by the compiler - instead being handed over to a much slower compiler supplied implementation of modulos. – Zv_oDD Mar 23 '23 at 13:47
0

In the trivial cases, every number that is an even multiple of a power of 2 is just shifted to the left (this doesn't apply when possibly altering the sign bit)

For example

10100

is 4 times

101

and 10100

is 2 time

1010

As for other multiples, they would have to be found by combining the outputs of two shifts. You might want to look up some primitive means of computer division, where division looks roughly like

x = a / b

implemented like

buffer = a
while a is bigger than b; do
  yes: subtract a from b
       add 1 to x
done

faster routines try to figure out higher level place values first, skipping lots of subtractions. All of these routine can be done bitwise; but it is a big pain. In the ALU these routines are done bitwise. Might want to look up a digital logic design book for more ideas.

Edwin Buck
  • 69,361
  • 7
  • 100
  • 138
  • Why does the MMU need to do divisions in bitwise operatos? Shouldn't that be done in ALU? – phuclv Mar 24 '15 at 05:47
  • Ah yes, in the ALU. My mistake, it's late over here. – Edwin Buck Mar 24 '15 at 05:55
  • This is a good reminder, thank you. I realized from testing this that it may be my data types that are causing other problems not my mask function because I tried to implement it using modules as is the more accepted way of doing this and I still get different numbers. – lauren Mar 24 '15 at 18:36
0

Ok, so I have discovered what the error was in my code and since the majority say that it is impossible to calculate whether a number is a multiple of another number using masks I figured I would share what I have learned. It is possible! - if you are using the correct data types that is.

The code given above works if y is declared as a constant unsigned long as x which was being passed in was also an unsigned long. The key point is not the long or constant part but that the number is unsigned. This sign bit causes miscalculation as the first place in the number indicates sign and when performing bitwise operations signs can get muddled.

So here is my code if we are looking for multiples of 16: const unsigned long y = 16; //declared globally in my case

Then an unsigned long is passed to the function which runs the following code: if(x&(y-1)){ //if not 0 then multiple of y x = x&~(y-1) + y; } x will now be the size of the nearest multiple of 16.

lauren
  • 11
  • 4