#include <stdio.h>\n\nint main() {\n int x = 18;\n\n if (x & 1) {\n printf(\"Impar\");\n } else {\n printf(\"Par\");\n }\n\n return 0;\n}<\/code><\/pre>\n\n\n\nClaramente a solu\u00e7\u00e3o utiliza um conhecimento adicional da linguagem C com a manipula\u00e7\u00e3o de bits, mas de que maneira isso torna a solu\u00e7\u00e3o mais eficiente? a opera\u00e7\u00e3o com bits costuma ser mais r\u00e1pida do que as opera\u00e7\u00f5es aritm\u00e9ticas e relacionais. A diferen\u00e7a \u00e9 bem pequena e para testar \u00e9 preciso realizar as opera\u00e7\u00f5es muitas vezes. No c\u00f3digo abaixo os c\u00e1lculos s\u00e3o feitos v\u00e1rias vezes. Utilizando o c\u00e1lculo da linha 6 do c\u00f3digo abaixo o tempo m\u00e9dio das execu\u00e7\u00f5es que executei ficaram em torno de 4,6 segundos, enquanto utilizando o c\u00e1lculo da linha 5 o tempo foi de 4,7 segundos. <\/p>\n\n\n\n
\u00c9 pouca diferen\u00e7a? sim. Ainda mais considerando que a opera\u00e7\u00e3o dificilmente seria realizada tantas vezes em uma solu\u00e7\u00e3o. Ent\u00e3o n\u00e3o existe problema algum em utilizar a solu\u00e7\u00e3o tradicional, mas \u00e9 interessante conhecer a alternativa com o bitwise<\/em>.<\/p>\n\n\n\n#include <stdio.h>\n\nint main() {\n for (int i=0; i < 2147483647; i++)\n (i % 2 == 1);\n \/\/(i & 1);\n\n return 0;\n}<\/code><\/pre>\n\n\n\nVeja que solicitei para o la\u00e7o for<\/em> executar 2.147.483.647 vezes e que esse \u00e9 o valor m\u00e1ximo que uma vari\u00e1vel int<\/em> pode assumir.<\/p>\n\n\n\nDado um conjunto de n\u00fameros onde todos os elementos ocorrem um n\u00famero par de vezes, exceto um desses valores, encontre o n\u00famero que ocorre um n\u00famero \u00edmpar de vezes.<\/p>\n\n\n\n
Para resolver, o algoritmo abaixo foi o primeiro que desenvolvi. Na fun\u00e7\u00e3o principal \u00e9 criado o vetor com alguns valores e chamada a fun\u00e7\u00e3o acharImpar()<\/em>. Essa fun\u00e7\u00e3o cria uma matriz com duas colunas na qual em cada linha ser\u00e3o armazenados cada valor encontrado do vetor e na coluna correspondente o n\u00famero de vezes que o valor foi encontrado. O n\u00famero de linhas da matriz considerou o maior tamanho dessa matriz: se todos os valores formarem um par + um n\u00famero sem par. No caso do meu vetor definido na fun\u00e7\u00e3o main()<\/em>, a matriz ter\u00e1 9\/2+1=5 linhas (lembre-se que 9\/2=4, uma vez que int\/int<\/em> resulta apenas na parte inteira da divis\u00e3o), embora apenas 4 ser\u00e3o realmente utilizadas.<\/p>\n\n\n\nO algoritmo se baseia em adicionar na matriz cada novo n\u00famero encontrado no vetor e contar quantas vezes cada um deles ocorre. Ao final \u00e9 buscado qual das contagens de ocorr\u00eancia resulta em um valor \u00edmpar e o valor correspondente \u00e9 retornado.<\/p>\n\n\n\n
#include <stdio.h>\n\nint acharImpar(int arr[], int n) {\n int i, j, qtd=0, mat[n\/2+1][2];\n\n for (i=0; i < n; i++) {\n \/\/verifica se o valor j\u00e1 est\u00e1 na matriz\n for (j=0; j < qtd; j++) {\n if (mat[j][0] == arr[i]) {\n mat[j][1]++;\n j = n;\n break;\n }\n }\n \/\/adiciona novo valor na matriz\n if (j != n) {\n mat[qtd][0] = arr[i];\n mat[qtd][1] = 1;\n qtd++;\n }\n }\n\n \/\/mostra a matriz\n for (i=0; i < qtd; i++) {\n printf(\"%i: %i \\n\", mat[i][0], mat[i][1]);\n }\n\n \/\/retorna a ocorr\u00eancia \u00edmpar\n for (i=0; i < qtd; i++) {\n if (mat[i][1]%2 == 1) {\n return mat[i][0];\n }\n }\n}\n\nint main(void) {\n int arr[] = { 10, 10, 11, 11, 11, 20, 12, 11, 12 };\n int n = sizeof(arr) \/ sizeof(arr[0]); \/\/calcula o tamanho do vetor\n printf(\"O valor que aparece um numero impar de vezes eh: %d \", acharImpar(arr, n));\n return 0;\n}\n<\/code><\/pre>\n\n\n\nAgora apresento uma solu\u00e7\u00e3o que utiliza uma opera\u00e7\u00e3o bitwise<\/em>. O c\u00f3digo abaixo para a fun\u00e7\u00e3o acharImpar()<\/em> utiliza o bitwise XOR<\/em> e obt\u00e9m o mesmo resultado da vers\u00e3o anterior. \u00c9 uma solu\u00e7\u00e3o mais sofisticada com certeza, mas mais econ\u00f4mica na aloca\u00e7\u00e3o de mem\u00f3ria pois dispensa a utiliza\u00e7\u00e3o da matriz. <\/p>\n\n\n\nint acharImpar(int arr[], int n) {\n int res = 0, i;\n for (i = 0; i < n; i++)\n res ^= arr[i];\n \/\/printf(\"%d: %d \\n\", arr[i], res);\n return res;\n}<\/code><\/pre>\n\n\n\nPara entender o que ocorre nesse c\u00f3digo, considere o que seria mostrado com o printf <\/em>da linha 5. O resultado \u00e9 mostrado abaixo. Veja que a cada intera\u00e7\u00e3o ocorrer uma soma e depois uma subtra\u00e7\u00e3o do valor do array. Assim, cada par de valor acaba se anulando, mesmo que n\u00e3o estejam consecutivamente, e fica sobrando apenas o valor que n\u00e3o tinha um par.<\/p>\n\n\n\n10: 10\n10: 0\n11: 11\n11: 0\n11: 11\n20: 31\n12: 19\n11: 24\n12: 20<\/code><\/pre>\n\n\n\nVeja que nessa solu\u00e7\u00e3o foi utilizado o princ\u00edpio do operador XOR, que funciona identificando um elemento que ocorre exclusivamente.<\/p>\n\n\n\n
Espero ter ajudado a entender um pouco mais sobre os operadores bitwise<\/em>. At\u00e9 uma pr\u00f3xima.<\/p>\n","protected":false},"excerpt":{"rendered":"Inicio com um exerc\u00edcio de algoritmos bastante tradicional e simples. O exerc\u00edcio consiste em determinar se um n\u00famero \u00e9 par ou \u00edmpar. Para resolver, o algoritmo abaixo foi o primeiro que desenvolvi e possivelmente \u00e9 a solu\u00e7\u00e3o que seria, de maneira similar, desenvolvida pela maioria das pessoas. Na solu\u00e7\u00e3o \u00e9 testado se o valor resultante […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"footnotes":""},"categories":[3,58],"tags":[],"class_list":["post-1342","post","type-post","status-publish","format-standard","hentry","category-c","category-codigo-com-analise"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t