Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is n= n ^1U<<i?

The problem I am facing here is to understand the change in the value of n in each iteration of the loop.
If you explain it by taking 2-3 iteration that will be awesome. correction -return value should be of 32 bit ....which is altering all bits 0->1 ans 1->0 .

long fun(long n)
{
    for(int i = 0; i < 32; i++)
        n = n ^ 1U << i;
    return n;
}   
like image 282
akshayroy Avatar asked Jul 21 '20 15:07

akshayroy


People also ask

What does 1U mean in C++?

1U is an unsigned value with the single bit 0 set, and all the other bits cleared. The << operator means "shift to the left". 1U << 0 means create a value with bit 0 set; 1U << 1 means create a value with bit 1 set; etc. Copy link CC BY-SA 2.5.

What is 1U in programming?

1U is unsigned. It can carry values twice as big, but without negative values. Depending on the environment, when using U, i can be a maximum of either 31 or 15, without causing an overflow. Without using U, i can be a maximum of 30 or 14. 31, 30 are for 32 bit int.

What does 0u mean in C++?

Thus ~0u means the maximum value of an object of type unsigned int when each bit of its internal representation is set to 1.

What is 5u in C?

5u means b00000101 , and because -1u is b11111111 in binary, you just subtract 4 from it, so -5u is b11111011 , which as an int , it is 251 .


2 Answers

i is counting.
1U << i is a single unsigned bit (LSB), which gets shifted in each turn by i to the left, i.e. it scans the bit positions, 0001, 0010, 0100, 1000 (read as binary please).
n = n ^ 1U << i sets n to a XOR of n and the shifted bit. I.e. it XORs n bit by bit completely.
The result is a completely inverted n.

Lets look at 4 iterations on the example 13, 1101 in binary.

1101 ^ 0001 is 1100
1100 ^ 0010 is 1110
1110 ^ 0100 is 1010
1010 ^ 1000 is 0010

0010 is 1101 ^ 1111

As Eric Postpischil mentions:

The parameter n to the function is a long, but the code iterates i through only 32 bits. It flips the low 32 bits in n, leaving high bits, if any, unaltered.
If long is 32 bits, then n = n ^ 1U << i is implementation-defined in some cases since the ^ of a long with an unsigned int will result in an unsigned long, and, if the resulting value cannot be represented in a long, the result is implementation-defined.

If we assume suitable input of n, e.g. being representable in the 32-bit wide type, or that the flipping of only lower bits is intentional, then that is not a problem.
Note with this and with Eric's comment, that a long is implicitly signed, which implies that the quasi MSB is not fully available for value representation (whether 2-complement or 1-complement or sign representation), because half of the range is used for negative values. Toggling it via a XOR then has potentially weird effects.

like image 180
Yunnosch Avatar answered Nov 02 '22 01:11

Yunnosch


It will flip the lower 32 bits in n. That total effect would be the same as just doing n ^= 0xFFFF.

In your code, n is long. If you're on a 32-bit compiler, then it'll have 32 bits, but it could be longer on other compilers.

If you unroll the loop, you get something like this:

n = n ^ 1U << 0;
n = n ^ 1U << 1;
n = n ^ 1U << 2;
...

Since << has higher precedence than ^, that will resolve to this:

n = n ^ 1;
n = n ^ 2;
n = n ^ 4;
...

The end effect is that it flips 32-bits of n, one bit at a time.

like image 21
Hines77 Avatar answered Nov 02 '22 01:11

Hines77