12 votes

Programming Challenge: Implementing bitwise operators.

Posted by Emerald_Knight (edited )
Tags: coding, challenge.programming

Background: Bitwise operators are operators that perform conditional operations at the binary level. These operators are bitwise AND &, bitwise OR |, bitwise XOR ^, and bitwise NOT ~, not to be confused with their logical operator counterparts, i.e. &&, ||, !=, and ! respectively.

Specifically, these operations take the binary values of the left- and right-hand terms and perform the conditional operation on each matching bit position between both values.

For instance, 3 | 4 takes the binary value 010 from 2 and 100 from 4. From left to right, we compare 0 || 1, 1 || 0, and 0 || 0 to get 110 as the resulting binary. This produces the integer value 6.

Goal: Your challenge is to implement one or more of these bitwise operators without using the native operators provided to you by your language of choice. Logical operators are allowed, however. These operators should work on integer values. These operators will likely take on the form of a function or method that accepts two arguments.

Bonus challenges:

  • Implement all of the operators.
  • Don't use any native binary conversion utilities.
  • Whether or not you implement all operators, write your code in such a way that allows for good code reusability.
  • For statically typed languages, handle integers of different types (e.g. int vs. uint).

Edit: Minor correction for the sake of accuracy, courtesy of @teaearlgraycold.

22 comments

  1. [7]
    teaearlgraycold
    Link
    It's usually represented by !=.

    XOR has no logical operator equivalent in most languages

    It's usually represented by !=.

    5 votes
    1. [3]
      Emerald_Knight
      Link Parent
      That's... correct? Shit, I didn't even think of that. I stand corrected. I'll edit accordingly. Thanks!

      That's... correct? Shit, I didn't even think of that. I stand corrected. I'll edit accordingly. Thanks!

      4 votes
      1. [2]
        teaearlgraycold
        Link Parent
        Ha ha, yeah. I don't think they ever mentioned it in school. I was looking for the XOR logical operator one day and after far too long I realized != was it.

        Ha ha, yeah. I don't think they ever mentioned it in school. I was looking for the XOR logical operator one day and after far too long I realized != was it.

        1 vote
        1. Emerald_Knight
          Link Parent
          It's a sneaky one for sure. The only time a one will be marked, and is guaranteed to be marked, anywhere in the binary is when the values aren't equal. I can't believe I never realized that before.

          It's a sneaky one for sure. The only time a one will be marked, and is guaranteed to be marked, anywhere in the binary is when the values aren't equal. I can't believe I never realized that before.

          1 vote
    2. [3]
      Social
      (edited )
      Link Parent
      ~~ In Python I believe it's ^~~

      ~~ In Python I believe it's ^~~

      1. [2]
        bme
        Link Parent
        that's the bitwise operator.

        that's the bitwise operator.

        3 votes
  2. [2]
    panic
    Link
    Once you have one, you can get the rest pretty easily: unsigned and(unsigned a, unsigned b) { unsigned result = 0; unsigned amount = 1; while (a && b) { if ((a % 2) && (b % 2)) result += amount;...

    Once you have one, you can get the rest pretty easily:

    unsigned and(unsigned a, unsigned b) {
  unsigned result = 0;
  unsigned amount = 1;
  while (a && b) {
    if ((a % 2) && (b % 2))
      result += amount;
    amount *= 2;
    a /= 2;
    b /= 2;
  }
  return result;
}

unsigned or(unsigned a, unsigned b) {
  return a + b - and(a, b);
}

unsigned xor(unsigned a, unsigned b) {
  return or(a, b) - and(a, b);
}

unsigned not(unsigned a) {
  return -(a + 1);
}
    5 votes
    1. Emerald_Knight
      Link Parent
      Very concise! I'll have to take a second look at this when I've gotten some sleep and thus have the patience to really understand it. It clearly makes use of some well-defined properties that take...

      Very concise! I'll have to take a second look at this when I've gotten some sleep and thus have the patience to really understand it. It clearly makes use of some well-defined properties that take a little more thought to wrap your head around :)

      1 vote
  3. Forty-Bot
    Link
    for ~ we do -(x++)

    for ~ we do -(x++)

    3 votes
  4. [6]
    Luca
    Link
    Oh hey, I actually did this at work last week. We had two one line, comma-separated strings we wanted to compare and find which words were unique. So I wrote up a quick python script to xor them.

    Oh hey, I actually did this at work last week. We had two one line, comma-separated strings we wanted to compare and find which words were unique. So I wrote up a quick python script to xor them.

    2 votes
    1. [5]
      Scion
      Link Parent
      Can you explain XOR to me?

      Can you explain XOR to me?

      3 votes
      1. [3]
        teaearlgraycold
        Link Parent
        You how when you have two light switches hooked up to the same light you can flip either one and the light will either turn on or off, even though you might be flipping the switch down to turn it...

        You how when you have two light switches hooked up to the same light you can flip either one and the light will either turn on or off, even though you might be flipping the switch down to turn it on and up to turn it off? That's XOR. You have two inputs. When they're equal the output is off and when they're not equal the output is on. This means that any change to either input will result in a change to the output.

        To put it another way, XOR defies the meme on reddit (and elsewhere) where someone asks if something is one way or another and the top response is just "yes". "Yes" only works for a question in the form "Is X a Y or a Z?" with an inclusive OR. Exclusive OR (XOR) does not allow both Y and Z to be true.

        2 votes
        1. [2]
          Scion
          Link Parent
          So inclusive (OR): Is it a [Y or Z]? Exclusive (XOR): Is it a [Y] or is it a [Z]?

          So inclusive (OR):

          Is it a [Y or Z]?

          Exclusive (XOR):

          Is it a [Y] or is it a [Z]?

          3 votes
      2. Emerald_Knight
        Link Parent
        Another way to think of XOR is that it's the "unrequited love" operator. That is, when one term "loves" the other but isn't loved back, the result is true. Was taught that analogy in a class back...

        Another way to think of XOR is that it's the "unrequited love" operator. That is, when one term "loves" the other but isn't loved back, the result is true.

        Was taught that analogy in a class back in college :)

        1 vote
  5. [4]
    ThirdSquid
    Link
    I actually really love the idea of posting challenges like this for programming. It's a really neat way to have fun with everything. I'd love to see more of these in the future. I'm going to give...

    I actually really love the idea of posting challenges like this for programming. It's a really neat way to have fun with everything. I'd love to see more of these in the future.

    I'm going to give this one a shot in the morning. We'll see how it goes!

    1 vote
    1. [3]
      Emerald_Knight
      Link Parent
      This is the third one that I'm aware of that was posted :)

      This is the third one that I'm aware of that was posted :)

      1. [2]
        ThirdSquid
        Link Parent
        How did I miss all these? I need to go track them down.

        How did I miss all these? I need to go track them down.

        1 vote
        1. Emerald_Knight
          Link Parent
          Pro tip: click on the "challenge" tag ;)

          Pro tip: click on the "challenge" tag ;)

  6. Emerald_Knight
    (edited )
    Link
    Here's my go at it. Edit: My solution took up a lot of screen real-estate, so I thought I would relocate it to a separate service.

    Here's my go at it.

    Edit: My solution took up a lot of screen real-estate, so I thought I would relocate it to a separate service.

  7. giggle
    Link
    The topic is very old but I think my entry is useful, its not a perfect answer because I cheated a bit because of shift operator but the main idea I want to show is that we can just use lookup...

    The topic is very old but I think my entry is useful, its not a perfect answer because I cheated a bit because of shift operator but the main idea I want to show is that we can just use lookup tables to solve this problem, I tried the best to make it appears as a truth table in the source.

    Also I just tested the input of the OP, here is the code: https://paste.debian.net/1287398/