Xor através de operações básicas. Operações lógicas básicas (e, ou, xor, não)

Neste artigo vou contar como funcionam as operações de bits. À primeira vista, eles podem parecer complicados e inúteis para você, mas na realidade não é esse o caso. É disso que tentarei convencê-lo.

Introdução

Os operadores bit a bit operam diretamente nos bits de um número, portanto os números nos exemplos estarão em binário.

Abordarei os seguintes operadores bit a bit:

• | (OR bit a bit),
• & (E bit a bit (E)),
• ^ (OU exclusivo (XOR)),
• ~ (Negação bit a bit (NÃO)),
• << (Побитовый сдвиг влево),
• >> (deslocamento bit a bit para a direita).

As operações de bits são estudadas na matemática discreta e também constituem a base da tecnologia digital, uma vez que nelas se baseia a lógica de funcionamento das portas lógicas, elementos básicos dos circuitos digitais. Na matemática discreta, como na engenharia digital, tabelas verdade são usadas para descrever seu funcionamento. As tabelas verdade, me parece, facilitam muito a compreensão das operações com bits, por isso irei apresentá-las neste artigo. No entanto, eles quase nunca são usados ​​em explicações de operadores bit a bit em linguagens de programação de alto nível.

Você também precisa saber sobre operadores de bits:

1. Alguns operadores bit a bit são semelhantes aos operadores com os quais você provavelmente está familiarizado (&&, ||). Isso ocorre porque eles são realmente semelhantes em alguns aspectos. No entanto, eles não devem ser confundidos em hipótese alguma.
2. A maioria das operações de bits são operações de atribuição composta.

OU bit a bit

OR bit a bit opera equivalente ao OR lógico, mas aplicado a cada par de bits de um número binário. O bit binário do resultado é 0 somente quando ambos os bits correspondentes são 0. Em todos os outros casos, o resultado binário é 1. Isto é, se tivermos a seguinte tabela verdade:

38 | 53 será assim:

Como resultado, obtemos 110111 2 ou 55 10.

E bit a bit

AND bit a bit é uma espécie de operação oposta de OR bit a bit. O dígito binário do resultado é 1 somente quando ambos os bits correspondentes dos operandos são iguais a 1. Em outras palavras, podemos dizer que os dígitos binários do número resultante são o resultado da multiplicação dos bits correspondentes do operando: 1x1 = 1, 1x0 = 0. A seguinte tabela verdade corresponde ao AND bit a bit:

Um exemplo de AND bit a bit trabalhando nas expressões 38 e 53:

Como resultado, obtemos 100100 2 ou 36 10.

Você pode usar o operador AND bit a bit para verificar se um número é par ou ímpar. Para inteiros, se o bit menos significativo for 1, então o número é ímpar (com base na conversão de binário para decimal). Por que isso é necessário se você pode usar apenas% 2? No meu computador, por exemplo, &1 roda 66% mais rápido. Um ótimo aumento de desempenho, deixe-me dizer.

OU Exclusivo (XOR)

A diferença entre XOR e OR bit a bit é que, para produzir 1, apenas um bit em um par pode ser 1:

Por exemplo, a expressão 138^43 será igual a...

… 10100001 2 ou 160 10

Usando ^ você pode alterar os valores de duas variáveis ​​(tendo o mesmo tipo de dados) sem usar uma variável temporária.

Você também pode criptografar texto usando OR exclusivo. Para fazer isso, você só precisa percorrer todos os caracteres e ^-los com o caractere-chave. Para uma cifra mais complexa, você pode usar uma sequência de caracteres:

String mensagem = "Esta é uma mensagem"; mensagem char = msg.toCharArray(); Chave de string = ".*)"; String criptografadaString = new String(); para(int eu = 0; eu< message.length; i++){ encryptedString += message[i]^key.toCharArray(); }

XOR não é o método de criptografia mais seguro, mas pode fazer parte do algoritmo de criptografia.

Negação bit a bit (NÃO)

A negação bit a bit inverte todos os bits do operando. Ou seja, o que era 1 se tornará 0 e vice-versa.

Por exemplo, aqui está a operação ~52:

O resultado será 203 10

Ao usar a negação bit a bit, o sinal do resultado será sempre o sinal oposto do número original (ao trabalhar com números assinados). Descubra por que isso acontece agora.

Código adicional

Aqui devo falar um pouco sobre como representar números inteiros negativos em um computador, ou seja, sobre o código do complemento de dois. Sem entrar em detalhes, é necessário facilitar a aritmética dos números binários.

A principal coisa que você precisa saber sobre números escritos em complemento de dois é que o bit mais significativo está assinado. Se for 0, então o número é positivo e coincide com a representação deste número em código direto, e se for 1, então é negativo. Ou seja, 10111101 é um número negativo e 01000011 é um número positivo.

Para converter um número negativo em seu complemento de dois, você precisa inverter todos os bits do número (essencialmente usando a negação bit a bit) e adicionar 1 ao resultado.

Por exemplo, se tivermos 109:

Com o método acima obtemos -109 no código de complemento de dois.
Uma explicação muito simplificada de código adicional acaba de ser apresentada e eu recomendo fortemente que você estude este tópico com mais detalhes.

Deslocamento bit a bit para a esquerda

As mudanças de bits são ligeiramente diferentes das operações de bits discutidas anteriormente. Um deslocamento bit a bit para a esquerda desloca os bits de seu operando N número de bits para a esquerda, começando com o bit menos significativo. Os espaços vazios após a mudança são preenchidos com zeros. Acontece assim:

Uma característica interessante de mudar para a esquerda em N posições é que isso equivale a multiplicar o número por 2 N . Então 43<<4 == 43*Math.pow(2,4) . Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.

Deslocamento bit a bit para a direita

Como você pode imaginar, >> desloca os bits do operando em um número especificado de bits para a direita.

Se o operando for positivo, os espaços vazios serão preenchidos com zeros. Se trabalharmos inicialmente com um número negativo, todos os espaços vazios à esquerda serão preenchidos com unidades. Isto é feito para preservar o sinal de acordo com o código adicional explicado anteriormente.

Como o deslocamento bit a bit para a direita é a operação oposta ao deslocamento bit a bit para a esquerda, é fácil adivinhar que deslocar um número para a direita por N número de posições também divide esse número por 2 N . Novamente, isso é muito mais rápido que a divisão normal.

Conclusão

Agora você sabe mais sobre operações de bits e não tem medo delas. Posso presumir que você não usará >>1 toda vez que dividir por 2. No entanto, é bom ter operações de bits em seu arsenal e agora você pode usá-las se necessário ou responder a uma pergunta complicada da entrevista.

Muitas vezes, para demonstrar as capacidades limitadas dos perceptrons de camada única na resolução de problemas, eles recorrem à consideração do chamado problema XOR – OU exclusivo.

A essência da tarefa é a seguinte. A função lógica XOR é dada - OR exclusivo. É uma função de dois argumentos, cada um dos quais pode ser zero ou um. Assume o valor quando um dos argumentos é igual a um, mas não ambos, caso contrário. O problema pode ser ilustrado usando um sistema de camada única, neurônio único e duas entradas, mostrado na figura abaixo.

Vamos denotar uma entrada por e a outra por , então todas as suas combinações possíveis consistirão em quatro pontos no plano. A tabela abaixo mostra a relação necessária entre entradas e saídas, onde as combinações de entradas que deveriam produzir uma saída zero são rotuladas e, uma única saída é rotulada e.

Um neurônio com duas entradas pode formar uma superfície de decisão na forma de uma linha reta arbitrária. Para que a rede implemente a função XOR especificada na tabela acima, é necessário posicionar a linha de forma que os pontos fiquem de um lado da linha e os pontos do outro. Tendo tentado traçar essa linha reta na figura abaixo, estamos convencidos de que isso é impossível. Isso significa que não importa quais valores sejam atribuídos aos pesos e limites, uma rede neural de camada única é incapaz de reproduzir a relação entre entrada e saída necessária para representar a função XOR.

No entanto, a função XOR é facilmente formada por uma rede de duas camadas e de várias maneiras. Vamos considerar um desses métodos. Vamos modernizar a rede da figura adicionando outra camada oculta de neurônios:

Observe que esta rede dado como está, ou seja, podemos assumir que ela já foi treinada. Os números acima das setas mostram os valores dos pesos sinápticos. Como função de ativação, usaremos uma função de salto único com limite tendo o seguinte gráfico:

Então o resultado da operação de tal rede neural pode ser apresentado na forma da tabela a seguir:

Cada um dos dois neurônios da primeira camada forma uma superfície de decisão na forma de uma linha reta arbitrária (divide o plano em dois semiplanos), e o neurônio da camada de saída combina essas duas soluções, formando uma superfície de decisão no forma de uma faixa formada por linhas retas paralelas dos neurônios da primeira camada:

A rede neural usada neste artigo para resolver o problema XOR é primitiva e não aproveita totalmente os recursos das redes multicamadas. Obviamente, multicamadas redes neurais têm maior poder de representação do que os de camada única apenas na presença de não linearidade. E nesta rede, uma função de ativação linear de limite é aplicada. Tal rede não pode ser treinada, por exemplo, usando um algoritmo de retropropagação.

Absolutamente todos os microcircuitos digitais consistem nos mesmos elementos lógicos - os “blocos de construção” de qualquer nó digital. É sobre isso que falaremos agora.

Elemento lógico- Este é um circuito que possui várias entradas e uma saída. Cada estado dos sinais nas entradas corresponde a um sinal específico na saída.

Então, quais são os elementos?

Elemento “E”

Caso contrário, é chamado de “conjuntor”.

Para entender como funciona, é necessário desenhar uma tabela que liste os estados de saída para qualquer combinação de sinais de entrada. Esta tabela é chamada " tabela verdade" As tabelas verdade são amplamente utilizadas na tecnologia digital para descrever a operação de circuitos lógicos.

Esta é a aparência do elemento “AND” e sua tabela verdade:

Já que você terá que se comunicar com tecnologia russa e burguesa. documentação, fornecerei símbolos gráficos simbólicos (GID) de elementos de acordo com nossos e não nossos padrões.

Observamos a tabela verdade e esclarecemos o princípio em nosso cérebro. Não é difícil de entender: uma unidade na saída do elemento “AND” ocorre apenas quando unidades são fornecidas a ambas as entradas. Isso explica o nome do elemento: as unidades devem estar em AMBOS uma E na outra entrada.

Se olharmos de forma um pouco diferente, podemos dizer o seguinte: a saída do elemento “AND” será zero se zero for aplicado a pelo menos uma de suas entradas. Vamos lembrar. Vamos em frente.

Elemento OU

Por outro lado, ele é chamado de “disjuntor”.

Nós admiramos:

Novamente, o nome fala por si.

Uma unidade aparece na saída quando uma unidade é aplicada a uma OU à outra OU a ambas as entradas ao mesmo tempo. Este elemento também pode ser chamado de elemento “AND” para lógica negativa: um zero em sua saída ocorre somente se zeros forem fornecidos para uma e para a segunda entrada.

Elemento NOTA

Mais frequentemente, é chamado de “inversor”.

Preciso dizer alguma coisa sobre o trabalho dele?

Elemento NAND

A porta NAND funciona exatamente da mesma forma que a porta AND, apenas o sinal de saída é completamente oposto. Onde o elemento “AND” deveria ter uma saída “0”, o elemento “AND-NOT” deveria ter uma. E vice-versa. Isso é fácil de entender a partir do circuito equivalente do elemento:

Elemento "NOR" (NOR)

A mesma história - um elemento “OR” com um inversor na saída.

O próximo camarada é um pouco mais astuto:
Elemento OR exclusivo (XOR)

Ele é assim:

A operação que ele executa costuma ser chamada de "módulo de adição 2". Na verdade, os somadores digitais são construídos sobre esses elementos.

Vejamos a tabela verdade. Quando é a unidade de saída? Correto: quando as entradas possuem sinais diferentes. Em um - 1, no outro - 0. Ele é tão astuto.

O circuito equivalente é algo assim:

Não é necessário memorizá-lo.

Na verdade, estes são os principais elementos lógicos. Absolutamente todos os microcircuitos digitais são construídos com base neles. Até mesmo o seu Pentium 4 favorito.

E por fim, vários microcircuitos contendo elementos digitais. Os números das pernas correspondentes do microcircuito são indicados próximos aos terminais dos elementos. Todos os chips listados aqui têm 14 pernas. A energia é fornecida às pernas 7 (-) e 14 (+). Tensão de alimentação – consulte a tabela do parágrafo anterior.

Indicado pela figura de linguagem “ou... ou...” A afirmação composta “ou A ou B” é verdadeira quando A ou B é verdadeiro, mas não ambos; V de outra forma a afirmação composta é falsa.

Aqueles. o resultado é verdadeiro (igual a 1), Se A não é igual a B (A≠B).

Esta operação é frequentemente comparada à disjunção porque são muito semelhantes em propriedades e ambas têm semelhanças com a conjunção “ou” na fala cotidiana. Compare as regras para estas operações:

1. verdadeiro se for verdade ou , ou ambos ao mesmo tempo.

2. verdadeiro se for verdade ou, Mas Não ambos ao mesmo tempo.

Operação exclui a última opção (“ambas ao mesmo tempo”) e por isso é chamada de “OR” exclusivo. Ambiguidade linguagem natural é que a conjunção “ou” pode ser usada em ambos os casos.

5. Implicação (consequência lógica)é formado pela combinação de duas afirmações em uma usando a figura de linguagem “se... então...”.

Gravação: A®B

Uma afirmação composta formada pela operação de implicação é falsa se e somente se uma conclusão falsa (segunda afirmação) segue de uma premissa verdadeira (a primeira afirmação).

Aqueles. se 1 implica 0, então o resultado é 0, em outros casos – 1.

Por exemplo, a afirmação “Se um número é divisível por 10, então é divisível por 5” é verdadeira porque tanto a primeira como a segunda afirmações são verdadeiras.

A afirmação “Se um número é divisível por 10, então é divisível por 3” é falsa porque uma conclusão falsa é tirada de uma premissa verdadeira.

"Este quadrilátero é um quadrado" (UM) E “Um círculo pode ser circunscrito em torno de um determinado quadrilátero” (EM). Então a declaração composta é lida como “Se um determinado quadrilátero for um quadrado, então um círculo pode ser desenhado em torno dele.”

Na linguagem comum, o conectivo "se... então" descreve a relação de causa e efeito entre as declarações. Mas nas operações lógicas o significado das afirmações não é levado em consideração. Apenas a sua verdade ou falsidade é considerada. Portanto, não se deve ficar envergonhado pela “falta de sentido” das implicações formadas por afirmações que são completamente não relacionadas em conteúdo. Por exemplo, assim: “se o Presidente dos Estados Unidos for um Democrata, então existem girafas em África”, “se uma melancia é uma baga, então há gasolina no posto de gasolina”.

6. A equivalência (igualdade lógica, ~ º Û) é formada pela combinação de duas afirmações em uma usando a figura de linguagem “...se e somente se...”

Uma afirmação composta formada por uma operação de equivalência é verdadeira se e somente se ambas as afirmações forem simultaneamente falsas ou verdadeiras.

Por exemplo, as afirmações “Um computador pode computar se e somente se estiver ligado” e “Um computador não pode computar se e somente se não estiver ligado” são verdadeiras porque ambas as afirmações simples são simultaneamente verdadeiras.

Tabelas verdade

Para cada afirmação composta (função lógica), é possível construir uma tabela verdade que determina sua verdade ou falsidade para todas as combinações possíveis dos valores iniciais de declarações simples.

Tabela verdade esta é uma visualização de tabela circuito lógico(operações), que lista todas as combinações possíveis dos valores verdade dos sinais de entrada (operandos) junto com o valor verdade do sinal de saída (resultado da operação) para cada uma dessas combinações.

Vamos refletir o acima discutido operações lógicas na tabela verdade:

Na álgebra proposicional, todas as funções lógicas por transformações lógicas podem ser reduzidas a três funções básicas: adição lógica, multiplicação lógica e negação lógica.

Vamos provar que a operação de implicação A®B é equivalente à expressão lógica:

A operação OR exclusivo (não equivalência, módulo de adição dois) é denotada por um símbolo e difere do OR lógico apenas quando A=1 e B=1.

Assim, a disparidade de duas afirmações X1 e X2 é chamada de afirmação Y que é verdadeira se e somente se uma dessas afirmações for verdadeira e a outra falsa.

A definição desta operação pode ser escrita na forma de uma tabela verdade (Tabela 6):

Tabela 6 – Tabela verdade da operação “OU EXCLUSIVO”

Como pode ser observado na Tabela 6, a lógica de funcionamento do elemento corresponde ao seu nome.

Este é o mesmo elemento “OR” com uma pequena diferença. Se o valor em ambas as entradas for igual a um valor lógico, então a saída do elemento “EXCLUSIVE OR”, ao contrário do elemento “OR”, não é um, mas zero.

A operação EXCLUSIVE OR na verdade compara dois dígitos binários para uma correspondência.

Cada conectivo lógico é considerado uma operação em declarações lógicas e possui nome e designação próprios (Tabela 7).

Tabela 7 – Operações lógicas básicas

1. Ordem das operações lógicas em uma expressão lógica complexa

O sistema de operações lógicas de inversão, conjunção e disjunção permite construir arbitrariamente complexos expressão lógica.

Ao calcular o valor de uma expressão lógica, é adotada uma certa ordem de operações lógicas.

1. Inversão.

2. Conjunção.

3. Disjunção.

4. Implicação.

5. Equivalência.

Parênteses são usados ​​para alterar a ordem especificada de operações.

1. Expressões Lógicas e Tabelas Verdade

   1. Expressões booleanas

Cada declaração composta pode ser expressa na forma de uma fórmula (expressão lógica), que inclui variáveis ​​lógicas, denotando declarações, e sinais de operações lógicas, denotando funções lógicas.

Para escrever uma declaração composta na forma de uma expressão lógica em uma linguagem formal (a linguagem da álgebra da lógica), em uma declaração composta é necessário identificar declarações simples e conexões lógicas entre elas.

Vamos escrever na forma de uma expressão lógica a afirmação composta “(2·2=5 ou 2∙2=4) e (2∙2≠5 ou 2∙ 2 ≠4)".

Vamos analisar a declaração composta. Ele contém duas declarações simples:

A = “2 2=5” - falso (0),

B = “2 2=4” - verdadeiro (1).

Então a instrução composta pode ser escrita da seguinte forma:

«( UMouEM) e (Ā ouEM)».

Agora você precisa escrever a afirmação na forma de uma expressão lógica, levando em consideração a sequência de operações lógicas. Ao realizar operações lógicas, é definida a seguinte ordem de execução:

inversão, conjunção, disjunção.

Parênteses podem ser usados ​​para alterar a ordem especificada:

F = (UMvEM) & (Ā vEM).

A verdade ou falsidade de enunciados compostos pode ser determinada de forma puramente formal, guiada pelas leis da álgebra proposicional, sem referência ao conteúdo semântico dos enunciados.

Vamos substituir os valores das variáveis ​​​​lógicas na expressão lógica e, usando as tabelas verdade das operações lógicas básicas, obtemos o valor da função lógica:

F= (A v B) & ( Ā v B) = (0 v 1) e (1 v 0) = 1 e 1 = 1.

Tabelas verdade

As tabelas nas quais as operações lógicas refletem os resultados dos cálculos de declarações complexas para vários valores das declarações simples originais são chamadas de tabelas verdade.

Declarações simples são denotadas por variáveis ​​(por exemplo, A e B).

Ao construir tabelas verdade, é aconselhável guiar-se por uma determinada sequência de ações:

é necessário determinar o número de linhas da tabela verdade. É igual à quantidade combinações possíveis valores de variáveis ​​​​lógicas incluídas em uma expressão lógica. Se o número de variáveis ​​lógicas for igual p, Que:

número de linhas = 2 n .

No nosso caso, a função lógica

possui 2 variáveis ​​e portanto o número de linhas na tabela verdade deve ser 4;

é necessário determinar o número de colunas da tabela verdade, que é igual ao número de variáveis ​​lógicas mais o número de operações lógicas.

No nosso caso, o número de variáveis ​​é dois: A e B, e o número de operações lógicas é cinco (Tabela 8), ou seja, o número de colunas da tabela verdade é sete;

é necessário construir uma tabela verdade com o número especificado de linhas e colunas, designar as colunas e inserir na tabela possíveis conjuntos de valores das variáveis ​​​​lógicas originais;

é necessário preencher a tabela verdade por colunas, realizando operações lógicas básicas na sequência necessária e de acordo com suas tabelas verdade.

Agora podemos determinar o valor de uma função booleana para qualquer conjunto de valores de variáveis ​​booleanas.

Tabela 8 – Tabela verdade de uma função lógica