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(")");
}
}
}

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.

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?

Re: Help me understand this code?

I don't know of any display methods that show leading 0s.

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)?

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.

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?

I appreciate your patience.

Re: Help me understand this code?

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.

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.

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

Re: Help me understand this code?

Thank you. I understand now. :)

Re: Help me understand this code?