# Help me understand this code?

• November 10th, 2013, 04:24 PM
Farkuldi
Help me understand this code?
Hi,

This is my first post here. I have have some code that prints out the possible 2-set combinations of numbers in a list, with some numbers on the right side and the rest of the numbers on the left side. However, I have been studying it for quite a while and I do not understand how it is doing what it is doing. Specifically, I do not understand the function of the bitwise right-shift and bitwise AND operators in the for loops. (In fact, this is the first time I have seen bitwise operators used in programming, so please forgive my ignorance).

I see how the bitwise left-shift operator is functioning to make the outer loop execute a certain number of times (which would determine how many combinations of numbers there would be, which would in turn be determined by the size of the original list, i.e. a list of length five would produce 2^5 - 2 combinations, because we have to have at least one number on each side of the list), but I do not understand how the right-shift and AND segment is working. It seems that it must be what determines which new list each number is in, but how? I do not understand what is happening here and would really appreciate any guidance you could give.

Thanks.

Code :

```public class SomeNumbers {   public static void main(String[] args) { int[] list = {1, 7, 6, 8, 9};     for (int i = 1; i < (1 << list.length) - 1; i++) { System.out.print("("); for (int j = 0; j < list.length; j++) { if (((i >> j) & 1) == 1) { System.out.print(list[j] + " "); } }   System.out.print(") ("); for (int j = 0; j < list.length; j++) { if (((i >> j) & 1) == 0) { System.out.print(list[j] + " ");   } } System.out.println(")"); }     }   }```
• November 10th, 2013, 04:47 PM
Norm
Re: Help me understand this code?
The AND operator is used to test if a bit is set. for example:
1010 AND 0001 is 0 meaning the rightmost bit is not set
1001 AND 0001 is 1 meaning the rightmost bit is set
If you have an int value (32 bits) and want to see if the 4th bit is a 1,
AND it with 00010000000000000000000000000 and test if the result is 0 meaning it is not set

The shift moves the bits by the number specified: 100 >> 2 gives 001

To see what the code is doing, add some println() statements and use one of the Integer class's methods to format the int values.
• November 10th, 2013, 05:42 PM
Farkuldi
Re: Help me understand this code?
Thank you. I am trying to make sense of it with some println() statements. I am using Integer.toBinaryString(int i), but it does not return the leading zeros. Doesn't Java have a way to show all the digits of a binary string, or would I have to write my own method if I wanted that?
• November 10th, 2013, 05:45 PM
Norm
Re: Help me understand this code?
I don't know of any display methods that show leading 0s.
• November 10th, 2013, 05:53 PM
Farkuldi
Re: Help me understand this code?
Thanks again. I don't seem to be getting anywhere, though. I am trying to see what the code does by putting the println() statements in as you suggested, but when I write
Code :

`System.out.println("binary " + Integer.toBinaryString(1 >> 2));`
,

for example, it just says 0. I am still not able to see what is happening. What Integer methods should I be using if not toBinaryString(int i)?
• November 10th, 2013, 06:05 PM
Norm
Re: Help me understand this code?
A 1 shifted right would go off the end. Try shifting 0x08 to the right 1, 2 or 3 places.
• November 12th, 2013, 12:02 PM
Farkuldi
Re: Help me understand this code?
Quote:

Originally Posted by Norm
A 1 shifted right would go off the end. Try shifting 0x08 to the right 1, 2 or 3 places.

Hi,

I am sorry I did not respond on Sunday.

I do see the way 1000 shifted right 1, 2, and 3 places becomes 0100, 0010, and 0001, thank you. That makes sense. I guess what I still do not understand is what it is doing in the context of this code. Specifically, this segment:

Code :

``` for (int j = 0; j < list.length; j++) { if (((i >> j) & 1) == 1) { System.out.print(list[j] + " "); } }```

This code is in another, outer loop, so let's say i = 1. On the first trip through the j loop, j = 0. So in the if clause, we shift i (which is 1) right by 0 places, which is still 1, and then apply the rightmost bit mask. So that should produce a 1, and we process the statement in the if clause.

However, on the next trip through the j loop, we have i = 1 and j = 1. So, what is the meaning of 1 >> 1? Would it be 0.1? Can you just have a decimal binary number, or do we need to take into account the twos complement representation or some other format? What happens now?

• November 12th, 2013, 12:20 PM
Norm
Re: Help me understand this code?
Quote:

1 >> 1
Print it out to see what it is.

Quote:

(results & 1) == 1)
That is the test to see if results has a 1 in the right most bit.
• November 12th, 2013, 01:19 PM
Farkuldi
Re: Help me understand this code?
Okay, it says it is zero. But why is it zero? I do not mean to belabor the point, but if 1 is shifted right one place, I do not see how that would produce zero unless there are more rules than have been stated here. Does everything to the right of the ones place just "fall off?" I would just like to understand what is happening.
• November 12th, 2013, 01:23 PM
Norm
Re: Help me understand this code?
Quote:

Does everything to the right of the ones place just "fall off?"
Yes, unless the shift does a wrap which moves the bit to the high end.

Think of shift as int division: 1/2 is 0
2(binary 10) shifted right 1 is 1 and 2/2 is 1
• November 12th, 2013, 02:27 PM
Farkuldi
Re: Help me understand this code?
Thank you. I understand now. :)
• November 12th, 2013, 02:37 PM
Norm
Re: Help me understand this code?