J'aime jouer au golf dc, mais je suis parfois frustré car je n'ai dcpas d'opérations au niveau du bit.

Défi

Fournir quatre fonctions nommées qui mettent en œuvre l'équivalent des c opérations binaires &, |, ~et ^( au niveau du bit, OR, NOT et XOR). Chaque fonction prendra deux opérandes ( ~n'en prend qu'un) qui sont des entiers non signés d'au moins 32 bits. Chaque fonction renverra un entier non signé de la même largeur de bits que les opérandes.

Restriction

Vous ne pouvez utiliser que des opérations prises en charge par dc. Ceux-ci sont:

• + - * / Addition, soustraction, multiplication et division arithmétiques
• ~ modulo (ou divmod si votre langue le prend en charge)
• ^ exponentiation
• | exponentiation modulaire
• v racine carrée
• > >= == != <= < opérateurs standard d'égalité / inégalité
• >> <<opérateurs de décalage de bits. dcn'a pas ces derniers, mais comme ils sont trivialement mis en œuvre en termes de division / multiplication par des puissances de 2, alors je les autoriserai.

Les structures de contrôle dcpeuvent être maladroitement construites à l'aide de macros (récursives) et d'opérations (in) d'égalité. Vous pouvez utiliser toutes les structures de contrôle intégrées de votre langue.

Vous pouvez également utiliser des opérateurs logiques && || ! , même s'ils ne sont pas directement disponibles dans dc.

Vous ne devez pas utiliser les opérateurs binaires & , |, ~et ^ou toutes les fonctions qui les mettent en œuvre trivialement.

De plus, vous ne devez pas utiliser d'opérateurs ou de fonctions de conversion de chaîne de base intégrés.

Veuillez également envisager de fournir un programme de test ou un extrait de compilateur en ligne (non inclus dans le score de golf) pour aider à vérifier votre réponse.

C, 134

Le préprocesseur C est assez amusant à abuser. Fondamentalement , cette macro définit les 3 fonctions, a, o, et x, pour and, oret , xorrespectivement. La seule différence dans l'algorithme pour ces opérations réside dans les critères de définition du bit dans le résultat.

notest la fonction 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)

Programme de testeur (prend beaucoup de temps, je n'ai pas passé de temps à l'optimiser, mais il teste tous les cas de test possibles, à l'exception de ceux liés à MAX_INT):

#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));
        }
    }

76 octets

ised n'a pas non plus d'opérations au niveau du bit - généralement ennuyeux, mais maintenant les bienvenus, car nous avons vraiment besoin implémenter.

Les fonctions seront stockées dans des emplacements de mémoire numérotés (pas de noms détaillés).

Conversion vers et depuis binaire:

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

NON pourrait l'être, @1{:$6::{1-$5::x}:}mais il est évidemment plus facile de simplement soustraire:

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

OU:

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

ET:

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

XOR:

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

Cela nous amènerait à 156 octets (avec des nouvelles lignes et des points-virgules). Un code de test serait simplement (PAS, OU, ET, XOR successivement, trouvé sous les noms $ 1, $ 2, $ 3, $ 4):

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

Mais bien sûr, OU et NON sont tout ce dont nous avons vraiment besoin et les choses peuvent être simplifiées:

@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:};

Cela fait 109 caractères. Lorsque les sauts de ligne et les points-virgules sont ignorés, et avec un peu plus de golf, nous avons 76 caractères:

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

Nim (537) (490)

Nim Compiler 0.10.2

Je cherchais une raison pour apprendre le nim alors c'est parti.

Pour le golf de code, j'ai utilisé des paramètres variables et des retours implicites. Les paramètres variables, selon la documentation, sont moins efficaces en pile. Personnellement, je trouve les retours implicites plus difficiles à lire et ne les utiliserais probablement que dans des procédures triviales.

Quant aux algorithmes, ils sont assez simples. Pour toutes les opérations sauf NOT, nous comparons chaque bit et les comparons manuellement à notre table de vérité attendue. Réglez chaque bit selon vos besoins en cours de route dans notre variable de sortie. Dans Nim, le résultat est la valeur de retour implicite.

Je ne savais pas si nous étions autorisés à utiliser OR et AND intégrés pour affirmer deux conditions booléennes, de sorte que la procédure notZero a été mise à leur 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)

Toujours à la recherche d'une meilleure méthode ...

Voici la version non écrasée et le harnais de test complet pour fonctionner sur votre propre machine.
Si vous souhaitez simplement exécuter quelques entrées, voici le cas de test Lite .

CJam, 71 octets

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

Explication

"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.";

Suite de tests

Ce code teste les exécutions de chacune de mes fonctions et, ou, et non, et xor 100 fois avec des entrées non signées 64 bits uniformément réparties et compare le résultat avec celui produit par l'opérateur intégré. En raison de l'utilisation gratuite de l'opérateur eval, il est assez lent et peut prendre jusqu'à environ une minute avec l'interprète en ligne. Mais si tout se passe bien, l'exécution devrait se terminer sans sortie, car les écarts trouvés sont imprimés.

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}?}/

Javascript 294 267

A pu raser quelques octets de plus avec les suggestions de @ AlexA. Et @ kennytm.

Les fonctions:

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

exemple:

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

production:

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