C # Primeiro 1 (da direita para a esquerda) no número binário

10

Estou tentando usar c # para encontrar o índice do primeiro 1 (da direita para a esquerda) na representação binária de um número. Por exemplo, uma vez que 100 em binário é:

0b1100100

O primeiro 1 está na terceira posição da direita, portanto deve render 3.

234 deve render 2, 0 deve render 0, etc.

Aqui está minha solução atual:

k < 1 ? 0 :(int)Math.Log(k & -k, 2) + 1;

Alguma maneira de tornar isso mais curto?

Eric Cepress
fonte
11
A dica óbvia é remover seu espaço em branco externo. Eu vejo 10 espaços que você pode remover facilmente.
James
Convert.ToString(k,2).IndexOf("1")é o que você deseja, ou algo semelhante, site errado.
Magic Octopus Urn
14
@ eleitores próximos - Por que os votos próximos? Penso que esta é uma questão de dicas sobre tópicos . Ou houve alguma alteração nas regras que eu perdi a esse respeito?
Digital Trauma

Respostas:

3

Se apenas o C # suportasse intrínsecos específicos à máquina ... Há uma única instrução que pode fazer isso na linguagem assembly x86 e também na maioria das outras arquiteturas de processador. Então você teria não apenas o código mais curto, mas provavelmente o mais rápido.

De fato, tornar esse código mais curto é um problema extremamente chato comparado a tornar esse código rápido . Existem todos os tipos de soluções realmente limpas, eficientes e de manipulação de bits, e você também pode considerar o uso de uma tabela de consulta.

Nada disso importa para o golfe, no entanto. Parece-me que sua solução atual é a melhor que você pode fazer. Obviamente, você pode remover o espaço em branco supérfluo:

k<1?0:(int)Math.Log(k&-k,2)+1

Eu pessoalmente o escreveria como:

k>0?(int)Math.Log(k&-k,2)+1:0

porque acho que é um pouco mais claro ter a direção do teste condicional dessa maneira, bem como compará-lo com zero, mas acho que são seis de uma maneira, meia dúzia da outra.

O C # não oferece suporte à conversão implícita de intpara o boolC e o C ++, portanto, você não pode realmente reduzir ainda mais o teste condicional.

Você também está preso ao elenco explícito de double(como retornou meu Math.Log) para int, pois o C # não permitirá que isso aconteça implicitamente. Obviamente, isso normalmente é uma coisa boa, porque indicaria que você tem um grande problema de desempenho aqui: promover um intpara a double, calcular o log de a doublee depois converter o doubleresultado em um intserá massivamente lento, então normalmente é algo que você gostaria de evitar. Mas esses são os tipos de perversões que você precisa suportar ao jogar código-golfe.


Eu tinha inicialmente pensado

k > 0
      ? ((k & -k) >> 1) + 1
      : 0

(ungolfed para maior clareza, é claro), que evita o logaritmo e, portanto, é uma melhoria no tamanho e na velocidade do código. Infelizmente, isso nem sempre recebe a resposta certa, e presumo que seja um requisito inflexível. :-) Especificamente, ele falhará se o valor de entrada ( k) for um fator de 8. Isso é corrigível, mas não sem tornar o código mais longo que a Math.Logversão.

Cody Gray
fonte
Observe que, para o código de golfe, Mathele teria que ser totalmente qualificado, para que sua outra versão fosse melhor, embora eu não tenha contado os bytes.
TheLethalCoder
Você quer dizer aquele que produz a saída errada? @the
Cody Gray
Bem, você disse que há uma correção, mas isso tornaria mais longo. Se a correção for mais curta do que quando a versão dos OPs incluir System., deverá ser mais curta e correta.
TheLethalCoder