0

I came up with a loop using bitwise operation, resulting in a number that has every other bit turned on (i.e. in case of 8-bit, 01010101).

In theory, my loop should work just fine, and it does work fine with uint32 and uint64, but not uint8 or uint16. I wonder why...

Here's the code:

@autoreleasepool {
    // a = 00000000
    uint32 a = 0;
    // b = 11111111
    uint32 b = ~a;
    // a = 11111111
    a = ~a;

    // if (a = 01010101) ~a = 10101010, a << 1 = 10101010
    while (~a != (a << 1)) {
        // 1st time: a << 1 = 11111110 = a
        // 2nd time: a << 1 = 11111010 = a
        a = a << 1;
        // 1st time: ~a = 00000001 = a
        // 2nd time: ~a = 00000101 = a
        a = ~a;
        // 1st time: a << 1 = 00000010 = a
        // 2nd time: a << 1 = 00001010 = a
        a = a << 1;
        // 1st time: b ^ a = 11111101 = a
        // 2nd time: b ^ a = 11110101 = a
        a = b ^ a;
    }

    NSLog(@"%x", a);
    NSLog(@"%u", b);



    // Apply the same loop to a bigger scale
    uint64 x = 0x0;
    uint64 y = ~x;
    x = ~x;

    while (~x != (x << 1)) {
        x = x << 1;
        x = ~x;
        x = x << 1;
        x = y ^ x;
    }

    NSLog(@"%llx", x);
    NSLog(@"%llu", x);
}
return 0;
phuclv
  • 37,963
  • 15
  • 156
  • 475
funct7
  • 3,407
  • 2
  • 27
  • 33
  • 1
    Welcome to SO! Can you provide some more information as to what isn't actually working? What output are you seeing? – Derek Oct 21 '13 at 13:39
  • Thanks Derek. The above codes are working fine, but if I replace uint32 with uint8 or uint16, the whole code goes into an infinite loop. I don't quite understand why... – funct7 Oct 21 '13 at 13:47
  • 2
    The failure is most likely due to integer promotion for variables smaller than int. – Paul R Oct 21 '13 at 14:01
  • 2
    `~a != (a << 1)` is always true if `a` is of a type smaller than `int`. – starblue Oct 21 '13 at 17:11
  • Thanks for the answers.. but is it possible to elaborate a little more? I'm new to the scene.. Why is ~a != (a << 1) when it is smaller than int and what does it mean by smaller than int? – funct7 Oct 25 '13 at 14:14

1 Answers1

1

By "smaller than int" starblue means sizeof(a) < sizeof(int). Because of the integer promotion rule, types narrower than int are always promoted to int before doing operations. For more information read Implicit type promotion rules

As a result, if a is uint8 or uint16, the top bits of ~a will always be 1 and can never be equal to a << 1

For example if a is uint16, running a few iterations we have a = 0x5555. After that point

(int)a = 0x00005555
    ~a = 0xFFFFAAAA
a << 1 = 0x0000AAAA

As you can see, ~a != (a << 1) and the program will loop forever

phuclv
  • 37,963
  • 15
  • 156
  • 475