Thread: Function return

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    3

    Function return

    Please help me understand what this function is checking and returning

    Code:
    int isPower2 (int myInt) {                                  
        return !(myInt>>31) & !!myInt & !(myInt & (myInt+(~1+1)));
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    The function name may give a clue. Test it with various input and see what you get. Then examine the code and see how it tallies with your observations.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907

    typo

    I'm assuming you have 32 bit integers - My guess is:
    Code:
    return !(myInt>>31) &                  /* Is not negative */
             !!myInt &                          /* Is not zero */
             !(myInt & (myInt+(~1+1))); /* Doesn't have more than 1 bit set */
    Fact - Beethoven wrote his first symphony in C

  4. #4
    Registered User poornaMoksha's Avatar
    Join Date
    Sep 2011
    Location
    India
    Posts
    41
    Which means that the function checks if the integer myInt is a power of 2 or not.
    Quote Originally Posted by Click_here View Post
    I'm assuming you have 32 bit integers - My guess is:
    Code:
    return !(myInt>>31) &                  /* Is not negative */
             !!myInt &                          /* Is not zero */
             !(myInt & (myInt+(~1+1))); /* Doesn't have more than 1 bit set */

  5. #5
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    I'll explain that last part:

    Code:
    !(myInt & (myInt+(~1+1))
    
    ~1+1 is the 2's complement of 1
    This is equal to -1
    
    for an unsigned int v (that is not 0)
    v & (v - 1) 
    will clear the least significant bit set
    
    consider this 4-bit example
    
    let v = 0101
    v-1 = 0100
    & this with v = 0100
    
    now consider v = 1100
    v-1 = 1011
    & this with v = 1000
    
    For something to be a power of 2, only 1 bit is going to be set ->
    So if you clear the LSB of the number (and it is the only bit set), you will end up with 0
    and !0 = 1
    So your function is returning -> if not 0 and not negitive and only one bit is set, the integer is a power of 2
    Last edited by Click_here; 10-02-2012 at 11:00 PM.
    Fact - Beethoven wrote his first symphony in C

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    This would normally be done on unsigned integers and is usually coded like this:
    v && !(v & (v - 1)); // From "Bit Twiddling Hacks" website

    But the OP's code is obviously trying to do it with restrictions.

    Which reminds me of the similar problem a week or two ago. May as well post my solution to that here. Still, there's got to be something simpler.
    Code:
    #include <stdio.h>
    #include <limits.h>
    
    int isitGreater(signed char x, signed char y) {
        x = x ^ y;
        y = (y ^ x ^ SCHAR_MIN) & (y ^ SCHAR_MAX);
        x = x | x >> 4;
        x = x | x >> 2;
        x = x | x >> 1;
        x = x & (SCHAR_MIN | ~(x >> 1));
        return !!(x & y);
    }
    
    int main(void) {
        signed char x = SCHAR_MIN, y = SCHAR_MIN;
        do {
            do {
                if ((x > y) != isitGreater(x, y))
                    printf("Error: %d %d\n", (int)x, (int)y);
            }while (y++ < SCHAR_MAX);
        }while (x++ < SCHAR_MAX);
        return 0;
    }
    Allowed operators: = & | ^ ~ >> ! (OP allowed +)
    Also allowed: return, parentheses, constants
    Not allowed: local vars, casts, control statements other than return.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  7. #7
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    Quote Originally Posted by poornaMoksha View Post
    Which means that the function checks if the integer myInt is a power of 2 or not.
    [edit]
    poornaMoksha - I see that you were just clarifying my post -> Ignore this comment.
    [/edit]

    I think that the OP may have been asking someone to explain the logic in the bitwise operation, not how to use the function
    Last edited by Click_here; 10-02-2012 at 11:24 PM.
    Fact - Beethoven wrote his first symphony in C

  8. #8
    Registered User
    Join Date
    Oct 2012
    Posts
    3
    That's right Click_here. Suppose my input to this function is

    int p = pow(2,n) -> where n is 1, 3, 5, 7, 9, 11, 13

    and now I am calling the function below,
    Code:
    int s = isPower2 (p)
    
    
    int isPower2 (int myInt) {                                  
        return !(myInt>>31) & !!myInt & !(myInt & (myInt+(~1+1)));
    }
    


    What should I expect the function isPower2 is returning. What is going on within this function. Laserlight as you have mentioned I tested with various inputs and got result which was not convincing to at least me Let me share the result,
    The returned result is listed below
    1
    1
    1
    1
    1
    1
    1
    1
    0 all the way down

    And if result of pow(2,n)
    2
    8
    128
    512
    2048
    8192
    2147483647 all the way down


    Let me describe the purpose of the program is to calculate Mersenne primes that are already lucky (lucky number --> 1, 3, 5, 7, 9, 11, 13).

  9. #9
    Registered User
    Join Date
    Nov 2011
    Location
    Buea, Cameroon
    Posts
    197
    form what i see its just bit manipulation tricks.. but with the double !! which i think cancels out in this case...

  10. #10
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by xboss View Post
    What should I expect the function isPower2 is returning. What is going on within this function. Laserlight as you have mentioned I tested with various inputs and got result which was not convincing to at least me


    Quote Originally Posted by poornaMoksha View Post
    Which means that the function checks if the integer myInt is a power of 2 or not.

    You should read all posts carefully.

    You get 1 as return value because that's the usual value for true in C.

    Bye, Andreas

  11. #11
    Registered User
    Join Date
    Oct 2012
    Posts
    3
    Thanks for your reply and time AndiPesti. I know 1 is value for return true and 0 is false. I was trying to explain "laserlight" the o/p I am getting from function isPower2. I am not questioning on what function is returning but how the function decide if return is true or false based on the input I am throwing in? Above all, I must say thank you all for your precious time and effort reading and responding my thread.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Function return a value
    By gr8npwrfl in forum C Programming
    Replies: 16
    Last Post: 07-16-2008, 10:10 PM
  2. Function Return
    By marquis1431 in forum C Programming
    Replies: 2
    Last Post: 04-14-2008, 11:33 PM
  3. Function return value
    By ursusman in forum C Programming
    Replies: 9
    Last Post: 11-28-2007, 07:17 AM
  4. Replies: 6
    Last Post: 04-09-2006, 04:32 PM
  5. return a value from a function
    By paulmedic555 in forum C Programming
    Replies: 4
    Last Post: 01-21-2005, 08:07 AM