Unwise bit operations

Question

I like to golf in dc, but I'm sometimes frustrated because dc doesn't have bitwise operations.

Challenge

Provide four named functions which implement the equivalent of the c bitwise operations &, |, ~ and ^ (bitwise AND, OR, NOT and XOR). Each function will take two operands (~ takes only one) which are at least 32-bit unsigned integers. Each function will return an unsigned integer of the same bit-width as the operands.

Restriction

You may only use operations that are supported by dc. These are:

• + - * / Arithmetic addition, subtraction, multiplication and division
• ~ modulo (or divmod if your language supports it)
• ^ exponentiation
• | modular exponentiation
• v square root
• > >= == != <= < standard equality/inequality operators
• >> << bit shift operators. dc doesn't have these, but since they are trivially implemented in terms of division/multiplication by powers of 2, then I will allow these.

Control structures in dc my be clumsily built using (recursive) macros and (in)equality operations. You may use whatever built-in control structures your language has.

You may also use logical operators && || !, even though these aren't directly available in dc.

You must not use the bitwise operators &, |, ~ and ^ or any functions that trivially implement them.

In addition you must not use built-in base-conversion-of-string operators or functions.

---

Please also consider providing a test program or online compiler snippet (not included in the golf score) to help verify your answer.

Answer 1

C, 134

The C preprocessor is pretty fun to abuse. Basically this macro defines the 3 functions, a, o, and x, for and, or, and xor respectively. The only difference in the algorithm for these operations is the criteria for setting the bit in the result.

not is the function n.

#define f(n,c)n(a,b){for(r=0,i=31;i+1;--i)if(((a>>i)%2+(b>>i)%2)c)r+=1<<i;return r;}
i,r;n(a){return 0xffffffff-a;}f(a,/2)f(o,)f(x,%2)

Tester program (takes a long time, I didn't spend any time optimizing it at all, but it does test every test case possible, beside MAX_INT related ones):

#define m_assert(expected, condition, actual)\
    if(!((expected) condition (actual)))\
        printf("assert fail @ line %i, expected: %x, actual %x, condition "#condition"\n", __LINE__, expected, actual);

int main()  {
    unsigned int j,k;
    for(j=0; j<0xffff; ++j)    {
        m_assert(~j, ==, n(j));
        for(k=0; k<0xffff; ++k)    {
            m_assert(j & k, ==, a(j,k));
            m_assert(j | k, ==, o(j,k));
            m_assert(j ^ k, ==, x(j,k));
        }
    }

Answer 2

ised 76 bytes

ised also doesn't have bitwise operations - usually annoying, but now welcome, because we really need to implement them.

Functions will be stored in numbered memory slots (no verbose names).

Conversion to and from binary:

@5{:x/2^[32]%2:};
@6{:x@:2^[32]:};

NOT could be @1{:$6::{1-$5::x}:} but it's obviously easier to just subtract:

@1{:2^32-x-1:};

OR:

@2{:$6::{$5::{x_0}:+$5::{x_1}>0}:};

AND:

@3{:$6::{$5::{x_0}:*$5::{x_1}}:};

XOR:

@4{:$6::{$5::{x_0}:<>$5::{x_1}}:};

This would bring us to 156 bytes (with newlines and semicolons). A test code would just be (NOT, OR, AND, XOR in succession, found under names $1,$2,$3,$4):

> $1::{6}
4294967289
> $2::{12 11}
15
> $3::{12 11}
8
> $4::{12 11}
7

---

But of course OR and NOT are all we really need and things can be simplified:

@1{:2^32-x-1:};
@2{:@+{2^U{?{$5::x}%32}}:};
@3{:${1 2 1}::x:};
@4{:$3::{$2::x${1 2}::x}:};
@5{:x/2^[32]%2:};

That's 109 characters. When newlines and semicolons are skipped, and with a bit more golfing, we have 76 characters:

@3{@1{:2^32-x-1:}@2{:@+{2^U{?{x/2^[32]%2}%32}}:}$1}@4{{:$2::x${1 2}::x:}$3};

Answer 3

Nim (537)(490)

Nim Compiler 0.10.2

I've been looking for a reason to learn nim so here we go.

For code golf, I have leveraged variable parameters and implicit returns. The variable parameters, per the documentation are less stack efficient. Personally, I find the implicit returns harder to read and would probably only use them in trivial procedures.

As for the algorithms, they are simple enough. For all operations except NOT, we compare each bit and manually compare them to our expected truth table. Set each bit as needed along the way in our output variable. In Nim, result is the implicit return value.

I wasn't sure if we were allowed to use built-in OR and AND for asserting two boolean conditions so the notZero procedure was put in their place.

proc s(x, y, b: var int)=
  x = x div 2
  y = y div 2
  b *= 2

proc n(x: var int): int =
  return -(x+1)

proc a(x, y: var int): int =
  var b = 1
  while x > 0 and y > 0:
    if (x mod 2  + y mod 2) == 2:
      result += b

    s(x,y,b)

proc o(x, y: var int): int =
  var b = 1
  while x + y > 0:
    if (x mod 2 + y mod 2) >= 1:
      result += b

    s(x,y,b)

proc r(x, y: var int): int =
  var b = 1
  while x + y > 0:
    if (x mod 2 + y mod 2) == 1:
      result += b

    s(x,y,b)

Still looking for a better method...

Here is the non-squished version plus full test harness to run on your own machine.
If you just want to run a couple of inputs, here is test case lite.

Answer 4

CJam, 71 bytes

{:F;0{:R;2md@2md@+F~!2I#*R+}64fI\;\;}:B{"2-"B}:A{'!B}:O{0SB}:N{'(B}:X];

Explanation

"B : UInt64 UInt64 String -> UInt64
 Computes a bitwise operation on the two given unsigned integers. The operation
 is defined by the logical inverse of the result of evaluating the given string
 given the sum of two input bits.";
{
  :F;             "Save the operation string.";
  0               "Initialize the result to 0.";
  {               "For I from 0 through 63:";
    :R;             "Save the result.";
    2md@2md@        "Divide each input by 2 and collect the remainders as the
                     next pair of bits to process.";
    +F~!            "Compute the logical inverse of the result of evaluating
                     the operation string given the sum of the two bits.";
    2I#*            "Adjust the resulting bit to be in the correct output
                     position by multiplying it by 2^I.";
    R+              "Add the location-adjusted bit to the result.";
  }64fI
  \;\;            "Clean up.";
}:B

"A : UInt64 UInt64 -> UInt64
 Computes the bitwise AND of the two given unsigned integers.
 This is done by passing the inputs along to B with an operation such that:
   bit_out = !((bit_in_1 + bit_in_2) - 2)";
{"2-"B}:A

"O : UInt64 UInt64 -> UInt64
 Computes the bitwise OR of the two given unsigned integers.
 This is done by passing the inputs along to B with an operation such that:
   bit_out = !(!(bit_in_1 + bit_in_2))";
{'!B}:O

"N : UInt64 -> UInt64
 Computes the bitwise NOT of the given unsigned integer.
 This is done by passing the input and 0 along to B with an operation such that:
   bit_out = !((bit_in + 0))";
{0SB}:N

"X : UInt64 UInt64 -> UInt64
 Computes the bitwise XOR of the two given unsigned integers.
 This is done by passing the inputs along to B with an operation such that:
   bit_out = !((bit_in_1 + bit_in_2) - 1)";
{'(B}:X

];              "Clean up.";

Test suite

This code tests runs of each of my and, or, not, and xor functions 100 times with uniformly-distributed 64-bit unsigned inputs and compares the result with that produced by the built-in operator. Due to gratuitous use of the eval operator, it's quite slow and may take up to about a minute with the online interpreter. But if all goes well, execution should end with no output, because any discrepancies found are printed.

N:L;
{:F;0{:R;2md@2md@+F~!2I#*R+}64fI\;\;}:B{"2-"B}:A{'!B}:O{0SB}:N{'(B}:X];
{;Y32#__mr*\mr+}2e2%2/{~:U;:V;"A&O|X^"2/{[{US@SV" = "UV5$~L}/9$2$={];}{]oLo}?}/"N~"[{U" = "U3$~Y64#(&L}/6$2$={];}{]oLo}?}/

Answer 5

JavaScript 294 267

Was able to shave off a few more bytes with @AlexA.'s and @kennytm's suggestions.

Functions:

B=(n,m,t)=>{for(var p=4294967296,y=0;p>=1;p/=2)y+=t=='x'&&(n>=p||m>=p)&& !(n>=p&&m>=p)?p:0,y+=t=='a'&&n>=p&&m>=p?p:0,y+=t=='o'&&(n>=p||m>=p)?p:0,n-=n>=p?p:0,m-=m>=p?p:0
return y}
N=(n)=>{return 4294967295-n}
A=(n,m)=>B(n,m,'a')
O=(n,m)=>B(n,m,'o')
X=(n,m)=>B(n,m,'x')

example:

var n = 300;
var m = 256;
console.log(X(n,m) + ", " + (n ^ m));
console.log(O(n,m) + ", " + (n | m));
console.log(A(n,m) + ", " + (n & m));
console.log(N(n) + ", " + (~n>>>0));
console.log(N(m) + ", " + (~m>>>0));

output:

44, 44
300, 300
256, 256
4294966995, 4294966995
4294967039, 4294967039