¿Cómo determinar si un número es impar o par sin operaciones mod o bit a bit?

Este desafío es extremadamente ineficiente, pero desafía su capacidad de pensar fuera de la caja para una solución creativa.

EDITAR :

Por favor crea una función. Además, aunque regex es una respuesta divertida, la función debe aceptar cualquier número válido.

ANTECEDENTES : Esta pregunta surge de mis primeros días de programación. La tarea para nuestro primer día de clase fue escribir un programa simple que imprimiera 'impar' o 'par'. Siendo el mocoso que era, no leí el libro que teníamos para la clase donde simplemente nos mostraba cómo usarlo%para determinar eso. Pasé aproximadamente media hora caminando de vuelta en mi habitación tratando de pensar en una forma de hacer esto y recordé de la conferencia que los números pueden perder y ganar precisión a medida que se lanzan de un tipo primitivo a otro. Por lo tanto, si tomó el número, lo dividió por dos y luego lo multiplicó de nuevo no era igual al número original, entonces sabría que el número era impar.

Me sorprendió al día siguiente, mientras nuestro instructor estaba evaluando nuestros programas, que pensaba que era la forma más original, aunque ineficiente, de resolver el problema.

En la mayoría de los lenguajes de programación, la división devuelve el cociente de enteros. Entonces puedes simplemente verificar esto

(i/2)*2==i

Pitón

print('even' if (-1)**n==1 else 'odd')

Cerebro *** (179)

Este es uno de los problemas más interesantes relacionados con la lógica condicional que he hecho en BF.

+[>,]<--------------------------------------->>+++++[>+++++++
++++++>+++++++++++++++<<-]>++++>++++<<+<+<-[>-<-[>+<-[>-<-[>+<-[>-<-[>
+<-[>-<-[>+<-[>-<[-]]]]]]]]]]>[>>>.<<-<-]>[>.<-]

Se necesita un ingreso de texto con un número. Si el número es par, sale E, y si es impar, sale O.

Estoy lo suficientemente orgulloso como para mostrar una forma más legible para los humanos:

+[>,]                                                   steps through input until it reaches eof.
<---------------------------------------                gets the numerical value of the last digit
>>+++++[>+++++++++++++>+++++++++++++++<<-]>++++>++++    store E and O
<<+<+<                                                  store a bit indicating parity, and a temporary bit
-[>-<                                                   !1
  -[>+<                                                 && !2
    -[>-<                                               && !3
      -[>+<                                             && !4
        -[>-<                                           && !5
          -[>+<                                         && !6
            -[>-<                                       && !7
              -[>+<                                     && !8
                -[>-<[-]]                               && !9
              ]
            ]
          ]
        ]
      ]
    ]
  ]
]
>[>>>.<<-<-]>[>.<-]                                     Display E or O based on the value of the parity bit.

Mathematica

SawtoothWave[x / 2] == 0
Exp[I Pi x] - 1 == 0
Sin[5 x / Pi] == 0

C

Multiplicado por sí mismo varias veces, cualquier número par se desbordará a 0 dado un número entero de tamaño finito, y cualquier número impar continuará teniendo al menos el conjunto de bits menos significativo.

#include "stdio.h"
long long input=123;
int main(){
    int a;
    for(a=6;a;a--){
        input*=input;
    }
    if(input){
        printf("Odd");
    }
    else{
        printf("Even");
    }
    return 0;
}

Editar: como una función simple:

int isOdd(long long input){
    int a;
    for(a=6;a;a--){
        input*=input;
    }
    return !!input;
}

Python (lento)

n=1234
while n > 1: n -= 2 #slow way of modulus.
print "eovdedn"[n::2]

JavaScript

/[02468]$/.test(i)

rinde truepara un número par. Esto solo funciona con enteros de tamaño razonable (por ejemplo, no una notación científica cuando se convierte en una cadena y no tiene una parte fraccional).

Pitón

Como no estoy realmente seguro de cuáles son los criterios de puntuación, aquí hay un montón de soluciones que he ideado por diversión. La mayoría de ellos usan abs(n)para soportar números negativos. La mayoría, si no todos, nunca deben usarse para un cálculo real.

Este es un poco aburrido:

from __future__ import division
def parity(n):
    """An even number is divisible by 2 without remainder."""
    return "Even" if n/2 == int(n/2) else "Odd"

def parity(n):
    """In base-10, an odd number's last digit is one of 1, 3, 5, 7, 9."""
    return "Odd" if str(n)[-1] in ('1', '3', '5', '7', '9') else "Even"

def parity(n):
    """An even number can be expressed as the sum of an integer with itself.

    Grossly, even absurdly inefficient.

    """
    n = abs(n)
    for i in range(n):
        if i + i == n:
            return "Even"
    return "Odd"

def parity(n):
    """An even number can be split into two equal groups."
    g1 = []
    g2 = []
    for i in range(abs(n)):
        g1.append(None) if len(g1) == len(g2) else g2.append(None)
    return "Even" if len(g1) == len(g2) else "Odd"

import ent # Download from: http://wstein.org/ent/ent_py
def parity(n):
    """An even number has 2 as a factor."""
    # This also uses modulo indirectly
    return "Even" if ent.factor(n)[0][0] == 2 else "Odd"

Y este es mi favorito, aunque desafortunadamente no funciona (como señala March Ho a continuación: solo porque todos los números pares son la suma de dos números primos, no significa que todos los números impares no lo sean).

import itertools
import ent    # Download from: http://wstein.org/ent/ent_py
def parity(n)
    """Assume Goldbach's Conjecture: all even numbers greater than 2 can
    be expressed as the sum of two primes.

    Not guaranteed to be efficient, or even succeed, for large n.

    """
    # A few quick checks
    if n in (-2, 0, 2): return "Even"
    elif n in (-1, 1): return "Odd"
    if n < 0: n = -n    # a bit faster than abs(n)
    # The primes generator uses the Sieve of Eratosthenes
    # and thus modulo, so this is a little bit cheating
    primes_to_n = ent.primes(n)
    # Still one more easy way out
    if primes_to_n[-1] == n: return "Odd"
    # Brutish!
    elif n in (p1+p2 for (p1, p2) in itertools.product(primes_to_n, primes_to_n)):
        return "Even"
    else:
        return "Odd"

Haskell

Por supuesto, esta no es de ninguna manera la solución creativa y pensante que estás buscando, pero ¿cuántas veces voy a publicar una respuesta de Haskell más corta que GolfScript? Es realmente una pena que esto no sea un código de golf.

odd

Pero más en serio:

data Parity = Even | Odd
            deriving (Show)

parity = p evens odds
  where p (x:xs) (y:ys) i | i == x = Even
                          | i == y = Odd
                          | otherwise = p xs ys i
        evens = interleave [0,2..] [-2,-4..]
        odds = interleave [1,3..] [-1,-3..]
        interleave (x:xs) ys = x : interleave ys xs

Usando una lectura deliberadamente perversa de la pregunta, "Cómo determinar si un número es par o impar", aquí hay una implementación en C (suponga booly truese define adecuadamente):

bool is_odd_or_even(int n)
{
    return true;
}

¿Qué, todavía no hay algoritmos aleatorios?

C

#include<stdio.h>
#include<stdlib.h>

void prt_parity_of(int n){
  int i,j=2;
  char o[]="eovdedn"
     , f[n=abs(n)]; for(i=n;i-->0;f[i]=1);

  while(j>1){
    while((i=rand()%n)
       == (j=rand()%n)
       || (f[i]&f[j]>0)
       && (f[i]=f[j]=0)
    );for(i=j=0; ++i<n; j+=f[i])
  ;}for(;j<7;j+=2)putchar(o[j]);
}

Empareja aleatoriamente números en el rango 0 .. n -1 hasta que queden menos de 2. Es bastante sorprendentemente ineficaz: O ( n ³ ).

Completamente diferente:

Haskell

import Data.Complex

ft f = (\ω -> sum[ f(t) * exp(0:+2*pi*ω*t) | t<-[-1,-0.9..1] ] )

data Parity = Even | Odd deriving (Show)

parity n
  | all (\(re:+im) -> abs re > abs im) [ft ((:+0).(^^n)) ω | ω<-[0..20]]  = Even
  | otherwise                                                             = Odd

Utiliza el hecho de que la transformada de Fourier de una función par (p \x->x^^4. Ej. ) Es real, mientras que la transformada de Fourier de una función impar es imaginaria.

Windows PowerShell

function OddOrEven([long]$n) {
  if (0,2,4,6,8 -contains "$n"[-1]-48) {
    "Even"
  } else {
    "Odd"
  }
}

1. Convertir a cadena
2. Elija la última letra (dígito) (esencialmente un mod 10).
3. Compruebe si es 0, 2, 4, 6 u 8.

Sin operadores bit a bit, sin módulo, según lo solicitado.

Coq, 103

Fixpoint even n:=match n with O=>true|S n=>odd n end with odd n:=match n with O=>false|S n=>even n end.

Por lo que puedo decir, esta es la primera entrada de coq en codegolf.

Incluso más corto (59):

Fixpoint even n:=match n with O=>true|S n=>negb(even n)end.

Rubí

n.odd?

Si desea imprimir el resultado:

f[n] = ->(n){puts n.odd?? 'odd' : 'even'}

Unlambda

El mundo necesita más Unlambda.

Unlambda tiene una ventaja asesina aquí: su valor predeterminado ( ejem ) para los números son números de la Iglesia, por lo que todo lo que se necesita es aplicarlos a la función binaria, no a la verdadera. ¡Fácil!

PD: Markdown y Unlambda definitivamente no están hechos el uno para el otro.

true  = i
false = `ki
not   = ``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki
even? = ``s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki

Verificación para los primeros enteros:

```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki`ki                   => i
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`kii                     => `ki
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki``s``s`kski           => i
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki``s``s`ksk``s``s`kski =>`ki

Golfscript

~,2/),1=\;

Pitón

print (["even"] + (["odd", "even"] * abs(n)))[abs(n)]

Rendimiento similar a la versión anterior. Funciona para 0 ahora.

Versión anterior incorrecta:

print ((["odd", "even"] * abs(n))[:abs(n)])[-1]

No particularmente eficiente; tiempo y memoria, obviamente, O (n): 32 ms por 1,000,000; 2,3 ms por 100000; 3.2 usec para 100. Funciona con números negativos. Lanza un error para 0, porque 0 no es par ni impar.

Fractran

[65/42,7/13,1/21,17/7,57/85,17/19,7/17,1/3]

aplicado a

63*2^abs(n)

produce ya sea 5si nes impar o1 si nes par.

Actualizar : mucho más corta pero no tan interesante:

[1/4](2^abs(n))

es 2para impar ny 1para par n.

MMIX (4 bytes)

Esto es una especie de trampa. No utilizo ni mod ni operaciones de violín. Es más bien que las pruebas de números pares / impares están integradas. Suponiendo que $3contiene el número a probar y el resultado entra en $2:

ZSEV $2,$3,1

conjuntos $2a 1si $3es par y en 0caso contrario. El mnemnorico ZSEVsignifica par cero y tiene la siguiente semántica:

ZSEV a,b,c: if (even b) a = c; else a = 0;

Para la línea anterior, mmixalgenera estos cuatro bytes de ensamblaje:

7F 02 03 01

Esquema

Esta es la solución más ineficiente que conozco.

(letrec ([even? (lambda (n)
                 (if (zero? n) "even"
                     (odd? (- n 2))))]
         [odd? (lambda (n)
                 (if (= n 1) "odd"
                     (even? (- n 2))))])
  (even? (read)))

Perl

Qué pasa

use Math::Trig;
print(cos(pi*@ARGV[0])>0?"even":"odd")

JavaScript, 36

function(i){while(i>0)i-=2;return!i}

Devuelve truesi incluso, falsesi no.

Perl

$n x '0' =~ /^(00)*$/

Pitón

zip((False, True)*(i*i), range(i*i))[-1][0]

probando el cuadrado de i, entonces también funciona para números negativos

F#

Recursión mutua por la victoria.

Un número n es par si es cero o (n-1) es impar.

Un número n es impar si no es igual a cero y (n-1) es par.

(abs añadido en caso de que alguien esté interesado en la paridad de números negativos)

let rec even n = n = 0 || odd (abs n - 1) 
    and odd n = n <> 0 && even (abs n - 1)

Clojure

  (defmacro even?[n]
  `(= 1 ~(concat (list *) (repeat n -1))))

¿Qué califica como operaciones bit a bit? Bajo el capó, es probable que la división de enteros por 2 se implemente como un cambio de bits.

Asumiendo que los cambios de bits no están disponibles:

C / C ++

(unsigned char)((unsigned char)(n > 0 ? n : -n) << 7) > 0 ? "odd" : "even"

editar Faltó algunos paréntesis y, en última instancia, cambió para eliminar un turno para que haga menos. Puede probar esto con lo siguiente (en * nix):

echo 'main(){ std::cout<< (unsigned char)((unsigned char)(n > 0 ? n : -n) << 7) > 0 \
        ? "odd\n" : "even\n";}' \
  | gcc --include iostream -x c++ -o blah -
./blah

... aunque en Linux / tcsh, tuve que escapar de la barra diagonal inversa a \npesar de que estaba entre comillas simples. Probé en little & big-endian, funciona correctamente en ambos. Además, copié a mano esto; la computadora con la que estoy publicando no tiene un compilador, por lo que puede tener errores.

x86 asm

            mov eax, n          # Get the value
            cmp eax,0           # Is it zero?
            jge pos_label       # If >= 0, skip the next part
            neg eax
pos_label:

.

            imul al, 128

o

            shl  al, 7

o

            lea  eax, [eax*8]    # Multiply by 2^3 (left-shift by 3 bits)
            lea  eax, [eax*8]    # ... now it's n*2^6
            lea  eax, [eax*2]    # ... 2^7, or left-shift by 7 bits

... seguido por:

            cmp al,  0          # Check whether the low byte in the low word is zero or not
            jz  even_label      # If it's zero, then it was an even number
            odd_label           # ... otherwise it wasn't

Alternativamente, el cambio y comparar cosas también se podría hacer de esta manera:

            sar al,1            # signed integer division by 2 on least-significant byte
            jc  odd_label       # jump if carry flag is set

En un procesador 68000, puede mover un valor de palabra de la dirección definida por el valor para probar:

 move.l <number to test>,a0
 move.w (a0),d0
 ; it's even if the next instruction is executed

y deje que la trampa de hardware para el error de dirección determine la naturaleza impar / par del valor; si se genera la excepción, el valor era impar; de lo contrario, el valor era par:

 <set up address error trap handler>
 move.l <pointer to even string>,d1
 move.l <number to test>,a0
 move.w (a0),d0
 <reset address error trap handler>
 <print string at d1>
 <end>

 address_error_trap_handler:
 move.l <pointer to odd string>,d1
 rte

No funciona en las CPU Intel x86, ya que son más flexibles sobre el acceso a datos.

Pitón

Decidí probar la solución más fea y confusa que se me ocurriera:

n=input();r=range(n+1)
print [j for i in zip(map(lambda x:str(bool(x))[4],[8&7for i in r]),
map(lambda x:str(x)[1],[[].sort()for x in r])) for j in i][n]

Imprime e si es par, o si es impar.

Q

Sigue restando 2 hasta x <2 y luego convierte a bool

{1b$-[;2]/[2<=;abs x]}