Talk:Bitwise operation

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 (talk • contribs).

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)Reply

Whats about Inversion and Complementing?

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

—The preceding unsigned comment was added by 88.72.207.149 (talk • contribs).

I do not recognize your "inversion" example. As for complementing you are describing Two's complement. Cburnett 13:09, 15 February 2007 (UTC)Reply

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)Reply

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)Reply

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

No. (b and 1) is implying a bitwise operation, not a logical operation. Oli Filth^{(talk|contribs)} 20:15, 10 February 2009 (UTC)Reply

"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)Reply

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)Reply

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

also http://graphics.stanford.edu/~seander/bithacks.html — Preceding unsigned comment added by 108.45.150.80 (talk) 00:53, 9 June 2018 (UTC)Reply

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)Reply

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.

Multiply is inherently more complex than add.
But processor designs may allocate faster and/or more execution units to compensate. Musaran (talk) 19:07, 7 October 2023 (UTC)Reply

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)Reply

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)Reply

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)Reply

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).Reply

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)Reply

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)Reply

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).Reply

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)Reply

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)Reply

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)Reply

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)Reply

Besides the already contained errors and missing statements, e.g.

x ^ x = 0

x ^ 0xFFFF = ~x

I am very reluctant to support real details in this section beyond the link to

Main article: Boolean algebra.

In principle, everything is already said in the section "Bitwise operators​". But the operators &,|,~,^ should be mentioned in this section in addition to AND, OR, NOT, XOR. –Nomen4Omen (talk) 17:26, 7 October 2020 (UTC)Reply

It seems that bit shifting is actually for compressing bytes by moving bits to save space and it turned out to not work since the innformation needs to be preserved. I think the wikipedia page on this topic needs to mention something about this but will likely be rejected due to dislike of it being called a scam? It doesn't seem to be a valid science to shift bits when information is lost as the whole idea is to preserve the information — Preceding unsigned comment added by 172.103.142.216 (talk • contribs)

@172.103.142.216: No, bit shifting isn't necessarily a scam! You do not know beforehand where the "information" is and which "innformation needs to be preserved". I'm absolutely sure that YOU haven't read everything that is available to be read and that YOU do not want to read everything. So in what you select, YOU are already cheating yourselves. –Nomen4Omen (talk) 08:46, 7 September 2021 (UTC)Reply

It says "given the bit pattern 0010 (decimal 2) the second and fourth bits may be toggled by a bitwise XOR with a bit pattern containing 1 in the second and fourth positions:" and gives this as an example:

    0010 (decimal 2)
XOR 1010 (decimal 10)
  = 1000 (decimal 8)

Isn't that toggling the first and third bits instead of the second and fourth bits? I guess the correct example would be:

    0010 (decimal 2)
XOR 0101 (decimal 5)
  = 0111 (decimal 7)

So either use the above as an example or change the phrase to "the first and third bits may be toggled by a bitwise XOR with a bit pattern containing 1 in the first and third positions" and keep the current example, which I guess would be better because it demonstrates XOR flipping both a 0 and a 1.

Douglasdcc (talk) 15:55, 10 April 2022 (UTC)Reply

There is no doubt at all, that a first bit toggles only a first bit, a second bit only a second bit, and a third bit only third bit, and so on. So your phrase "the first and third bits may be toggled by a bitwise XOR with a bit pattern containing 1 in the first and third positions" is correct, and your example

    0010 (decimal 2)
XOR 0101 (decimal 5)
  = 0111 (decimal 7)

as well. But there is no real toggling in your example, because the two operands do not have two 1s on a matching position. And a 0 does not toggle anything.

Maybe, the indexing of the positions is the problem? The first position is index 0 and the fourth position index 3:

    4321 (-th position)
    3210 (bit index)
    0010
XOR 1010
  = 1000

and this should be made more clear.

You seem to know that the decimal representation is not input, but result only. —Nomen4Omen (talk) 17:01, 10 April 2022 (UTC)Reply

the 4 bit integer illustrations for different operations have no reference on how to interpret them—and are not self evident—and effectively have no communicative value except as technical reference. that is to say, if you come to the page as an introduction to bitwise operation you have no indication on how to make sense of large, title graphics for each operation. by contrast, the caption provides a link for 4bit, which has digressive, lateral value but anyone trying to understand bitwise operation would understand what 4 bits are and have a sense of what a 4 bit integer might be.

this is a basic failure to be encyclical and accessible as even to a reader with a basic and rough coding background (this author) they are illegible. that's fine, it's an esoteric subject—the failure is in not providing any key or name for further investigation for any non computer scientist. Abaczkowski (talk) 17:11, 25 June 2022 (UTC)Reply

Thanks for pointing out. Perhaps you or someone can improve them by editing their captions. –Novem Linguae (talk) 18:07, 25 June 2022 (UTC)Reply

Just noticed the truth table is quite inconsistent in how it chooses to represent the logical operators. Swapping out ↛ for NIMPLY and If/then for IMPLY would be more fitting for an article about logic in computers, no? There's also the inconsistency in Converse NIMPLY being represented here as Xq while Converse IMPLY is represented as Then/if. Iarmethodil (talk) 20:52, 9 February 2024 (UTC)Reply