Talk:Bit manipulation

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing ??? This article has not yet received a rating on the project's importance scale.

I added the ^{[dubious – discuss]} tag to the following

In most cases, the programmer would choose the former method. If it was necessary to find the minimum of two integers millions of times per second, the programmer might exploit his knowledge of binary representation of integers and come up with the latter method. Since that method does not use branching, it runs faster on some processors.

Already the first part is not true, in most cases the programmer would use the MIN(x,y) macro implemented as (x<y)?x:y, or a min(x,y) procedure that would be inlined by the compiler and avoid duplicate evaluation of x,y if this would eb a concern. But the main problem is the last phrase; since so far I only know counter-examples providing evidence against the truth of the statement, so even if it is m-m-maybe conceivable that the idea could apply (and still, I could not think of a microprogram realizing that situation), if there is no commercially available CPU with this property, then I don't think it is relevant and the statement should better be removed since it would only create confusion in > 99% of the cases. For current processors as AMD and Pentium my tests provide evidence for the fact that (x<y)?x:y virtually takes no time (almost all of the time of the loop, being needed to decrement & zero test the counter and branch back), while the "complicated" solution takes over 20% of the total time.— MFH:Talk 15:59, 5 June 2008 (UTC)Reply

In principle the non-branching method would work better because the processor cannot predict the branching outcome, and therefore wouldn't have to wait for the result of the boolean test; but since I haven't tested this I will go with what you said. Also, most processors would only have one "pipeline" for the thread that is finding the minimum of the integers, meaning that all of the information is going to have to go through at some point. Heuvelton (talk) 01:25, 22 June 2008 (UTC)Reply

On a simple mips machine, or RISC architecture in general both can be emulated with 5 assembly mnemonics, however the second uses less branching, which means it avoids pipeline stalls and is therefore faster on average. Although in this case the branches are short so would not cause cache misses, various architectures would slow down due to this, including AMD and Intel, and a simple experiment isn't proof that it is wrong. Also, DSPs where bit twiddling is more likely would likely reveal this result. Video cards may also benefit from such manipulation. Using a standard library definition avoids the point and is a totally different problem, specifically since this is not a language specific issue. Anonymous

(the previous paragraph was not signed, my stuff starts here) Whatever the outcome, please definitelly leave the example there, as it is very informational. I program for many years but I never realized this is possible. It doesn't matter which is faster - that always depends on other factors. Ypocat (talk) 19:23, 4 September 2008 (UTC)Reply

----The results will be compiler/language & executing architecture dependent AND actual flow dependent. A good compiler/RT arch should spew out a correct imple..but that is (still) far from always true.---- —Preceding unsigned comment added by 80.11.117.11 (talk) 10:19, 24 November 2008 (UTC)Reply

The program snippet is an "obvious" division loop, but that's so very bad programmatically (2 divides per bit??) that I would never instruct anyone to do that. As an algorithm, yes, we may think of it that way, since a power of 2 is 2*2*...*2 and after casting away all the 2s, there'll be only a factor of 1 left. I wouldn't want to tempt someone to compile and actually run that program. I think just a technically concise text description, or a pseudocode snippet would adequately convey the idea. Then, we proceed to the bit-code to implement it, since that is what the article is about. The section drowns in the irrelevant example. Sbalfour (talk) 19:39, 13 November 2019 (UTC)Reply

Fixed. Sbalfour (talk) 21:22, 13 November 2019 (UTC)Reply

The article has too much context specific text: i.e. the C language, the GNU compiler, the X86 architecture. Bit manipulation has nothing to do with any of these. The article should focus on the operations, and what interesting results can be obtained elegantly and efficiently by use of them. If necessary, present expressions in an appropriate pseudocode or mathematical notation. The rest of the context stuff should vanish. Sbalfour (talk) 19:54, 13 November 2019 (UTC)Reply

Substantially revised. More work required.Sbalfour (talk) 21:22, 13 November 2019 (UTC)Reply