dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 3 of 4 FirstFirst 1234 LastLast
Results 31 to 45 of 56

Thread: Implementing If-then-else without branching

  1. #31
    Join Date
    May 1999
    Location
    Southern California
    Posts
    12,266
    As best as I understand, the original question asked here was reproduced from the memory of the person interviewed. I think that the replies saying the question is not a good question support my belief that the actual question asked by the interviewer was not the same as what was asked in the original question here. Of course, I am not saying that the question the interviewer asked was a good question, but it might have been more appropriate than the one here.
    "Signature":
    My web site is Simple Samples.
    C# Corner Editor

  2. #32
    Join Date
    May 2000
    Location
    KY, USA
    Posts
    18,652
    Originally posted by Sam Hobbs
    As best as I understand, the original question asked here was reproduced from the memory of the person interviewed. I think that the replies saying the question is not a good question support my belief that the actual question asked by the interviewer was not the same as what was asked in the original question here. Of course, I am not saying that the question the interviewer asked was a good question, but it might have been more appropriate than the one here.
    You already stated that before
    I think if a prospective employer were to ask the question as it was initially asked, they would get plenty of complaints.
    and got a response indicating that this wasn't the case...
    Sorry Sam but I haven't rephrased the question. I posted the one that was given to me. What I posted here were the words of the interviewer. He presented the question the same way I presented here.

  3. #33
    Join Date
    Feb 2004
    Location
    Helsinki, Finland
    Posts
    31
    Originally posted by Sam Hobbs
    I have not re-read this thread after reading your response, but I sure don't remember anyone saying that branching is bad. The original question (supposedly as asked by the interviewer) asked not to use branching but that is the only place I remember where branching was perhaps suggested as bad.
    My point exactly. No-one questioned the need for branches in general, so I felt compelled to offer an alternate viewpoint.
    IPC? This discussion has such remote relevance to interprocess communication as to make IPC irrelevant.
    Instructions Per Clock. A poor way of comparing the effectiveness of different CPU architectures, but easy to use in a discussion.
    Since you used such strong words, I will reply correspondingly. I notice that sometimes people try harder to explain to others what it is that the others don't understand and then blame them for not listening. Often the truth is that the person trying to explain needs to listen and understand. I think you are trying to show off your knowledge of low-level processor design but you did not spend much time understanding this discussion.
    Now what is this all about? Never mind.

  4. #34
    Join Date
    Aug 2001
    Location
    Stockholm, Sweden
    Posts
    1,664
    I would like to add some comments:

    1. I would probably never write this type of obsfucated code for any serious stuff (unless there is a very good reason).
    2. I generally don't like tests like this, for several reasons. One is that it doesn't prove much on how skilled you're as programmer/developer. In this example, it may prove that you know the bitwise operators and how 2-complement arithmetics work.
    3. Synthetic Being, your solution is fine, but you didn't follow the rules (see first post in this thread). There are many better solution if one could use other operators, than those stated in the first post.

    As most of you probably, I really love solving problems... This interview question was just one of them problems needed to be solved.

    It took me a few minutes (maybe even 20 or so)... I first got stuck on that left-shift zero (<<0) isn't the same as multiplying with zero (*0), because it would easily have been solved if one could use * operator:
    y * (!!x) + z * (!x)
    but that wasn't allowed. I still went with the left-shift operator:
    y << (!!x) + z << (!x)
    This is the same as the math expressions:
    [for x = 0]: y + 2z
    [for x <> 0]: 2y + z
    So, if I only could substract y and z, the problem would be solved:
    [for x = 0]: y + 2z - y - z = z
    [for x <> 0]: 2y + z - y - z = y
    Substraction without using the minus operator is quite easy though on 2-complement machines/environments--just invert it and add 1:
    (y << (!!x)) + (z << (!x)) + (~y + 1) + (~z + 1)
    (Iíve intentionally used more parentheses than necessary to make it clearer.)
    Ok, that's at least how I solved this problem.

    Have fun,
    /Jonas

  5. #35
    Join Date
    Feb 2004
    Posts
    138
    I am sorry again for interupting but I think Synthetic Being ()'s answer were really great !!!
    But could anyone tell me where I can find materials about such branches, how do you Synthetic Being know so much about that ?
    I think if I start another thread, it would be like a waste right ? so I ask you here
    I would like to read about them..

    Thanks a lot

  6. #36
    Join Date
    May 2000
    Location
    KY, USA
    Posts
    18,652
    Originally posted by Synthetic Being
    Instructions Per Clock. A poor way of comparing the effectiveness of different CPU architectures, but easy to use in a discussion.
    Well...IPC usually stands for Interprocess communication...so I guess it is simply a misunderstanding here...

  7. #37
    Join Date
    Feb 2004
    Location
    Helsinki, Finland
    Posts
    31
    Originally posted by j0nas
    3. Synthetic Being, your solution is fine, but you didn't follow the rules (see first post in this thread). There are many better solution if one could use other operators, than those stated in the first post.
    Right. In that case the zero/not zero comparisons (x != 0) and (x == 0) have to be replaced by (!!x) and (!x). Now also the letter in addition to the spirit of the assignment has been fulfilled. FYI, these produce identical assembly output.

  8. #38
    Join Date
    Feb 2004
    Location
    Helsinki, Finland
    Posts
    31
    Originally posted by Charleston
    But could anyone tell me where I can find materials about such branches, how do you Synthetic Being know so much about that ?
    I think if I start another thread, it would be like a waste right ? so I ask you here
    OK. If you want to know about the x86-specific quirks then read these. Obviously it's always nice to know some assembly for any architecture and the basic inner workings of CPUs in general. That's likely to make you a better programmer in the long run.

    http://fatphil.org/x86/pentopt/
    http://www.intel.com/design/pentium4/manuals/248966.htm

  9. #39
    Join Date
    Feb 2004
    Posts
    138
    Originally posted by Synthetic Being
    OK. If you want to know about the x86-specific quirks then read these. Obviously it's always nice to know some assembly for any architecture and the basic inner workings of CPUs in general. That's likely to make you a better programmer in the long run.

    http://fatphil.org/x86/pentopt/
    http://www.intel.com/design/pentium4/manuals/248966.htm
    Thank you....

  10. #40
    Join Date
    May 1999
    Location
    Southern California
    Posts
    12,266
    Originally posted by Synthetic Being
    Instructions Per Clock. A poor way of comparing the effectiveness of different CPU architectures, but easy to use in a discussion.
    In this context, IPC will not be understood as meaning Instructions Per Clock.
    "Signature":
    My web site is Simple Samples.
    C# Corner Editor

  11. #41
    Join Date
    Sep 2002
    Location
    Maryland - Fear The Turtle!
    Posts
    7,537
    meh...my two cents. The question is only relevant or irrelevant when placed in the proper context.

    irrelevant interview question: how many jelly beans does it take to fill a 57 chevy carburetor (unless we are talking how do you deal with the stupid customer requirements phaze)

    relevant interview question (when in context): how do you call a non-exported system service function.


    Synthetic Being and yves get my gold star for civilized post/response discussion. Would that I could aspire to such a loftness

  12. #42
    Join Date
    Oct 2002
    Location
    Singapore
    Posts
    3,128
    Great explanation, Synthetic Being! Should there be a need in the future, that's definitely one more trick that I can use for optimization.

  13. #43
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: Implementing If-then-else without branching

    Quote Originally Posted by j0nas
    (y << (!!x)) + (z << (!x)) + (~y + 1) + (~z + 1)
    It can be done a bit simpler (conceptually):
    Code:
    ( (!x+(~0)) & y ) | ( (!!x+(~0)) & z )
    !x is either 1 or 0, so !x-1 is 0 or 0xff...f, the binary mask that then can be &ed with selecting value (and !!x-1 with another one).

    The shortest (in symbols) I found:
    Code:
    !x+~0&y|1+~!x&z
    -15 symbols. Is there a shorter solution?
    Last edited by RoboTact; January 2nd, 2005 at 03:34 PM.
    "Programs must be written for people to read, and only incidentally for machines to execute."

  14. #44
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: Implementing If-then-else without branching

    Quote Originally Posted by kabootar
    How can the if-then-else clause be implmented without branching. Only operators allowed are ~, !, ^, &, +, |, <<, >>.

    For eg:
    Code:
    int Compare( int x, int y, int z )
    {
    	if ( x == 0 )
    		return y;
    	else
    		return z;
    }
    For an interviewer the question really only has merit as a means to see how a prospective job applicant handles the problem.

    There is no real practical use to the problem at hand. In my classes for optimizing, I really need to drill out 'old habits' of trying to outsmart the compiler.
    Most of the time, the compiler is a LOT better at generating efficient code for any trivial (and even not so trivial solution).

    If there was a REAL performance benefit to be made, don't you think the compiler designers would have added this in their optimizer already? Compiler benchmarks are a big issue, and they add a LOT more complicated type optimisations than this.

    Most of the time, if you want to get better performance, you have to rethink the program at a higher level. Put your brains at work to find a better design, and let the compiler twiddle the bits for you.

    Trying to optimize something like this will yield unreadable code, and little performance benefit (it may even be slower).


    Anyhow... probably the best solution (size/performance wise) you could give (sorry jonas and synthetic )...

    return y ^ (((x==0)-1) & (z ^ y));

    which translates in a releasebuild to.

    Code:
       mov         edx,dword ptr [esp+4] 
       mov         eax,dword ptr [esp+8] 
       xor         ecx,ecx 
       test        edx,edx 
       sete        cl   
       push        esi  
       mov         esi,dword ptr [esp+10h] 
       mov         edx,eax 
       xor         edx,esi 
       pop         esi  
       dec         ecx  
       and         ecx,edx 
      xor         eax,ecx 
       ret
    which is slightly smaller/faster than synthetic's solution. The branch solution however is faster (on average).

    I leave it up to you to try and figure out WHY the above bit of code works

    Of course, writing code like this doesn't make your code more readable ;-)

  15. #45
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: Implementing If-then-else without branching

    That gives 13-symbols solution (following the rules):
    Code:
    z^!x+~0&(z^y)
    It becomes as simple as would be treated as a good programming style after a couple more improvements...

    btw VisualC++6 compiled it without that push/pop esi excess: this may be because there was only that code in the whole function and no other register distribution issues involved:
    Code:
    mov     edx, [esp+4]
    mov     eax, [esp+0Ch]
    xor     ecx, ecx
    test    edx, edx
    mov     edx, [esp+8]
    setz    cl
    dec     ecx
    xor     edx, eax
    and     ecx, edx
    xor     eax, ecx
    retn
    Last edited by RoboTact; January 2nd, 2005 at 07:57 PM.
    "Programs must be written for people to read, and only incidentally for machines to execute."

Page 3 of 4 FirstFirst 1234 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)