Talk:Bitwise operation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics 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.
Mathematics rating:
Start Class
Low Priority
 Field: Discrete mathematics
WikiProject Electronics (Rated Start-class, Low-importance)
WikiProject icon This article is part of WikiProject Electronics, an attempt to provide a standard approach to writing articles about electronics on Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks. Leave messages at the project talk page
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
 

C/C++ incorrect[edit]

The description of C/C++ is incorrect insofar as unsigned integers (representing [0..(2^N)-1]) act with the character of a "logical shift", whereas signed integers (representing [-2^(N-1)..0.. 2^(N-1)-1]) are in some circumstances not defined and are left up to the implementation, regarding the presence of upper order 1 bits subsequent to right-shift.

As described in the ANSI C standard section 6.5.7 [5], the operation is actually only indeterminate if the number is negative:

http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n843.htm

—The preceding unsigned comment was added by 150.169.8.72 (talkcontribs).

Hello, I should have looked at the discussion page first! I also noticed this issue and I edited a sentence that stated C/C++ compilers always use logical shifts even with signed integers. It was probably a wrong formulation, results are always undefined only if the right operand is negative. Here is the source for the C language: JTC1/SC22/WG14 N843, section 6.5.7: "Bitwise shift operators", pages 91 and 92 (http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n843.htm). I do not have any information concerning C++ about this subject.
--Acetate (talk) 13:14, 27 June 2008 (UTC)

Whats about Inversion and Complementing?[edit]

Whats about Inversion and Complementing?

  • Inversion 110 -> 011
  • Complementing 110 -> 001

—The preceding unsigned comment was added by 88.72.207.149 (talkcontribs).

I do not recognize your "inversion" example. As for complementing you are describing Two's complement. Cburnett 13:09, 15 February 2007 (UTC)
He's probably talking about the operation that reverses the order of bits in a n-bytes integer. I don't know whether it deserves a section as it is built upon other basic bit-wise operators.
--Acetate (talk) 13:18, 27 June 2008 (UTC)


Application incorrect[edit]

Hello,

This algorithm is wrong. Try a = 2, b = 10

c := 0 while b ≠ 0

   if (b and 1) ≠ 0
       c := c + a
       shift a left by one
   shift b right by one

return c —Preceding unsigned comment added by 137.151.174.176 (talk) 01:18, 6 November 2008 (UTC)

Pseudo-code[edit]

Isn't "if (b and 1) ≠ 0" equivalent to "if b ≠ 0"? Robogymnast (talk) 19:58, 10 February 2009 (UTC)

No. (b and 1) is implying a bitwise operation, not a logical operation. Oli Filth(talk|contribs) 20:15, 10 February 2009 (UTC)
"AND 1" clears all bits except the LSB (bit 0). I think it is more clear to write "if (B AND 1) = 1 then".
If you want to test bit 3 for example you'll write "if (B AND 8) = 8 then". SvenPB (talk) 12:10, 26 February 2009 (UTC)

Optimization/Tricks[edit]

I've seen extensive development of bitwise "tricks" in practice, but don't see it mentioned in this article. Is there such an article that this could link to, as a "See Also" item, or would it make sense to develop the idea within this article? 70.250.179.253 (talk) 02:14, 14 March 2010 (UTC)

In further reading, I've found Hacker's Delight as a candidate article. 70.250.179.253 (talk) 02:40, 14 March 2010 (UTC)

Bit-counting[edit]

To determine whether the third bit is 1, a bitwise AND is applied to it and another bit pattern containing 1 in the third bit:

   0011

AND 0010

 = 0010

Third bit? That took me a while to comprehend. Well, I would rather count bits from right to left, so with the binary '0100' the '1' would be the 2nd (if first bit is 0th) or the 3rd bit (if first bit is 1st). The author who put this into the article might have counted from left to right (well, obviously eh). Dunno what's "more common", but I've never ever said that with a binary number '10000000', the "first bit was 1". No, it's the 7th. -andy 212.114.254.107 (talk) 13:38, 19 March 2010 (UTC)

multiply slower than add?[edit]

Is it fair to say, as the lead does in other words, that multiplication is slower than addition?

Modern processors such as Intel Itanium and Xeon have a combined "multiply and add" instruction as, I believe, their *only* variants of these instructions, and execute it in one cycle. (Of course, a straight add or multiply without the other is achieved just by using the identity functions x + 0 = x and x * 1 = x). This is hugely beneficial in real applications where multiply-then-add is extremely common, for example, for array indexing (of course an optimizer might well have other strategies for dealing with that) and for very common linear equations, eg. graphics transforms (again, this may well be done these days on the GPU).

I don't want to make this article an enormous encomium to the benefits of multiply-and-add, but I wonder if this general statement in the lead is still true enough "for modern processors" to be stated that way. Of course, all floating-point instructions are implicitly multiply-and-add anyway, and the lead does not narrow it down to integer instructions, which it probably should.

I should appreciate your views.

S.

Bitshifting speed[edit]

The article states that on modern architectures, bitwise operations are not usually faster than addition, but does not specifically make that claim for bitshifting. Does this mean that x * 2 will generally be no faster than x + x, for example? what about x * 2 + x vs. x * 3? Eebster the Great (talk) 19:45, 20 May 2010 (UTC)

Furthermore, the first reference (http://www.fredosaurus.com/notes-cpp/expressions/bitops.html) does not claim that "on modern architectures ... bitwise operations are generally the same speed as addition". Its only speed-related claims are:

  • "However, I believe most newer CPUs don't depend on the shift distance."
  • "On some older computers is was faster to shift instead of multiply or divide by a power of two." 82.150.248.28 (talk) 14:34, 29 March 2011 (UTC)

power consumption[edit]

So the speed of multiply/divide is as fast as bitwise operations in current cpus. But what about power consumption? Rtdrury (talk) 02:16, 19 July 2010 (UTC)

Need to specify register length for NOT operator[edit]

The text "This example uses an 8-bit register:" is given for the shift example. But for consistency, surely the NOT example needs to say "This example uses an 4-bit register:". A 3 bit register would convert from 111 to 000 --Skytopia (talk) 23:49, 29 June 2011 (UTC).

What are the bitwise operators in C?[edit]

This article does not answer the above question. please add following to the passage:

  • biwise AND operator in C: &
  • bitwise OR operator in C: | — Preceding unsigned comment added by 2.145.223.233 (talk) 09:28, 31 January 2012 (UTC)

Two's complement description incorrect?[edit]

The section on bitwise NOT describes two's complement as negating the value and subtracting one. Shouldn't this be adding one? — Preceding unsigned comment added by 99.235.242.51 (talk) 20:26, 24 March 2012 (UTC)

It would be adding one. But I think in the section you are referring to, bitwise complement actually means ones’ complement or not, and inverse actually means the negative arithmetic value. Perhaps it could do with some clarifying. Vadmium (talk, contribs) 03:32, 25 March 2012 (UTC).

Application suggestion[edit]

I'm surprised nobody has mentioned how bitwise operators are useful for enums. something like this: http://www.codeproject.com/Articles/13740/The-Beginner-s-Guide-to-Using-Enum-Flags I'm not sure how much detail to go into here, though. 174.6.72.195 (talk) 02:11, 29 December 2012 (UTC)

Addition in bit operations and zero-testing, corrected & commented[edit]

The article currently (2013-08-11Z) contains this example at the end of the "Applications" section:

c = b and a
while a ≠ 0
    c = b and a
    b = b xor a
    left shift c by 1
    a = c

return b

The first line is unneeded, because register c is always initialised first in the loop and not used at the end outside the loop. With that line removed and furthermore, with # marking a comment until the end of a line:

while a != 0            # Each iteration results in the same sum for a + b,[1]
                        #  until a is zero at which point b holds the sum.[1]
    c := b and a        # This separates out all bits set in both a, b.
                            # All these bits would carry if bits were added individually,
                            #  that is, if the bits in a, b were to be added bit-wise.
    b := b xor a        # This clears in b the bits set in both a, b (previously saved to c),
                        #  and sets in b all the other bits set in a.
                            # To xor is, in fact, the same operation as bit-wise addition
                            #  thus a xor b adds each bit pair of a, b while discarding carries.
    left shift c by 1   # Multiply the carrying bits' values by two.
                            # This results in the carry bits, which form the carry value.[1]
    a := c              # Save value to add in the next iteration.
                            # The saved value is this iteration's carry value, to be added to
                            #  this iteration's b. Loop until no carry occurs (until a is zero).

return b

[1] Of course, if an overflow (carry out of the registers' width) occurs, then the sum of the original values won't be preserved and won't eventually be returned, though the sum modulo 2(registers' width in bits) would be both preserved and eventually returned. The carry occurs in the left shift, which in a way is the only operation that moves any bits to have them act in other bits' positions.

Left here because it doesn't seem appropriate to put any of this into the article, except for the removal of the unneeded line. --82.113.121.184 (talk) 22:51, 11 August 2013 (UTC)

Shifts considered not "bit-wise" but NOT considered "bitwise"?[edit]

There is a caveat in the article mentioning shifts are not technically bit-wise because it does not apply to corresponding pairs of bits. Would it then make sense to apply the same caveat to the NOT operator section, as it applies to only one set of bits? Bcjordan (talk) 16:43, 22 January 2014 (UTC)

The last example, ancient Egyptian multiplication, is a summation not multiplication[edit]

The last example in the page

while a ≠ 0
    c = b and a
    b = b xor a
    left shift c by 1
    a = c
 
return b

is a summation not multiplication of a and b

Try this code with golang playground

package main
 
import "fmt"
 
func eq1(a, b int) int {
 
    c := 0
    for b!=0 {
        if (b & 1) != 0 {
            c += a
        }
 
        a = a << 1
        b = b >> 1
    }
 
    return c
}
 
func eq2(a, b int) int {
    var c int
    for a!=0 {
        c = b & a
        b = b ^ a
        c = c << 1
        a = c
 
    }
 
    return b
}
 
func main() {
    fmt.Println(eq1(2,3))
    fmt.Println(eq2(2,3))
}

you will see that the result of the first equation is multiplication, but with the second equation, which is the same as the example mentioned in the page, is summation not multiplication.

You're right. Went ahead and corrected the article; the first pseudocode sample is in fact an implementation of ancient Egyptian multiplication, and the second is an implementation of addition. Please check it out. — Dsimic (talk | contribs) 08:03, 31 March 2014 (UTC)