Replicating the function of a for loop using only bitwise operators

Question

I'm trying to replicate the function of a loop using only bitwise and certain operators including ! ~ & ^ | + << >>

int loop(int x) {
   for (int i = 1; i < 32; i += 2)
     if ((x & (1 << i)) == 0)
       return 0;
   return 1; 
}

Im unsure however how to replicate the accumulating nature of a loop using just these operators. I understand shifting << >> will allow me to multiply and divide. However manipulation using ! ~ & ^ ~ has proven more difficult. Any Tips?

http://www.tutorialspoint.com/cprogramming/c_operators.htm

Edit: I understand how the addition of bits can be achieved, however not how such an output can be achieved without first calling a while or for loop.

First think about what the function is actually doing - it's testing all the odd-numbered bits to see if they are all 1. So how would you do that in a single operation using bitwise operators ? (Think masks.) — Paul R
– Paul R, Commented Jul 18, 2016 at 10:00
@Silverfin: your logic is a bit off - you probably want to use a mask of all odd bits (0xaaaaaaaa), since these are the bits you are interested in. Then the function would just be return (n & mask) == mask; (you don't need an if). If you can't use == then think about how to implement that with further bitwise operations. — Paul R
– Paul R, Commented Jul 18, 2016 at 10:12
Yes, that looks promising, assuming you are allowed to use the logical NOT operator (!). — Paul R
– Paul R, Commented Jul 18, 2016 at 10:28
@PaulR I can, i've got a better grasp of things. thanks you. — Silverfin
– Silverfin, Commented Jul 18, 2016 at 10:40

4386427 · Accepted Answer · 2016-07-18 10:40:33Z

6

Maybe this can help:

int loop(int x) {
    x = x & 0xaaaaaaaa; // Set all even numbered bits in x to zero
    x = x ^ 0xaaaaaaaa; // If all odd numbered bits in x are 1, x becomes zero
    x = !x;             // The operation returns 1 if x is zero - otherwise 0
    return x;
}

edited Jul 18, 2016 at 10:40

answered Jul 18, 2016 at 10:38

4386427

44.7k4 gold badges44 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mario Dekena Over a year ago

Maybe i dont get it, but this does return a value greater then 1, doesnt it?

Mario Dekena Over a year ago

Oh i see, because ! is logical not. Clever!

Mario Dekena · Accepted Answer · 2016-07-18 10:34:54Z

0

Your code tests all odd bits and returns 1 if all of them are set. You can use this bitmask: ...0101 0101 0101 Which, for 32 bits is 0xAAAAAAAA. Then you take your value und bitwise-and it. If the result is the same as your mask, it means all bits are set.

int testOddBits(int x) {
    return (x & 0xAAAAAAAA) == 0xAAAAAAAA;
}

edited Jul 18, 2016 at 10:34

answered Jul 18, 2016 at 10:27

Mario Dekena

8436 silver badges20 bronze badges

11 Comments

Mario Dekena Over a year ago

@PaulR no it isnt, because the return is int, not bool.

Mario Dekena Over a year ago

oh i see, i didnt get you. i though you would suggest return x & 0xAAAAAAAA. You are right, sry.

Mario Dekena Over a year ago

@Silverfin Your function does not return multiple times. You can only return once. The function will be aborted, and the single value will be returned.

Tommylee2k Over a year ago

Funny to see how each_and_every answer in [C] is downvoted even tho it's a correct answer to the question, and may (nor may not) have a small slip. And funny how all these "experts" keep their mouth shut instead of answering, and then nitpick those who do.

Tommylee2k Over a year ago

@RaulR as far as i've understood, the problem is the loop, and ?: is explained in the link provided by the OP. so I cannot see why Mario's answer is "not helpful", it hints to using a mask to AND with it, rather than using a loop. Let the OP decide if the return type matters or not

|

Collectives™ on Stack Overflow

Replicating the function of a for loop using only bitwise operators

2 Answers 2

2 Comments

11 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

11 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related