-1

I am currently taking Intro programming classes. We are learning Java SE (eventually moving up to Java EE). I have a grasp on most things, but I hit a wall with bitwise manipulation and masking. For example:

EDITED HERE: I want to figure out if a number is divisible by 3 and 5, but not 2. The only requirements is that I can not use % to find the answer, it has to be in a method call, and I have to use masking and bitwise operands.

I already learned how to determine if a number is odd or even with this:

public static boolean isEven(int num) {
        return ((num & 1) == 0);
    }

I understand what the bitwise operands (&, |, ^, >> , <<) do but can't actually implement them properly. Our book also does not have information on this, it's from our teachers notes. I'm not asking for just the answer, I need to understand how it actually works.

Michael George
  • 25
  • 1
  • 5
  • Try writing out the numbers by hand, in binary, then use those operators – OneCricketeer Nov 03 '18 at 22:28
  • I edited the original problem to the actual one I need to solve. I just didn't think it'd be right to get the answer without working it out myself, so I switched numbers. Divisible by 3 and 5, but not 2 is the actual problem – Michael George Nov 03 '18 at 22:35
  • Also, how is the isEven wrong? It gives me the correct answers in the actual code (using NetBeans). – Michael George Nov 03 '18 at 22:37
  • 2
    Again, try writing out 3,5,6,9,10,12, etc in binary, and look for a pattern where 6, 10, and 12 should return false for some condition – OneCricketeer Nov 03 '18 at 22:38
  • @cricket_007 is there an obvious solution? There's summing the nibbles, or multiplying by 0xeeeeeeef, both seem hard to discover – harold Nov 03 '18 at 22:51
  • So we did learn how to extract bits using hex: – Michael George Nov 03 '18 at 23:32
  • 1
    See https://stackoverflow.com/questions/31957961/check-division-by-3-with-binary-operations and https://stackoverflow.com/questions/17113660/divisiblity-of-5-without-using-and-operator – Stephen C Nov 03 '18 at 23:39

1 Answers1

0

These are pretty tricky unless your prof has actually shown you how to do this sort of thing. I'll do 3, and you figure out how to do 5.

This works because 4 == 1 mod 3:

static boolean isDivisibleBy3(int n)
{
    while(n<0 || n>3) {
        n = (n&3) + (n>>2);
    }
    return (n==3 || n==0)
}

n&3 gets the lower two bits. (n>>2) gets the rest of the bits and divides by 4. Because 4 == 1 mod 3, dividing by 4 doesn't change the remainder mod 3. Then we add them back together and get a smaller number with the same remainder as the one we started with.

Repeat until we get a number less than 4. At that point it's not going to get any smaller.

There are faster ways to do this, but this way is the easiest to understand.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87