Elenco não assinado com assinatura eficiente evitando o comportamento definido pela implementação

Eu quero definir uma function que leva um unsigned int como argumento e retorna um módulo congruente int UINT_MAX + 1 para o argumento.

Uma primeira tentativa pode ser assim:

 int unsigned_to_signed(unsigned n) { return static_cast(n); } 

Porém, como qualquer advogado de idiomas sabe, a conversão de valores não assinados para assinados para valores maiores que INT_MAX é definida pela implementação.

Eu quero implementar isso de tal forma que (a) ele só dependa do comportamento exigido pela especificação; e (b) compila em um não-op em qualquer máquina moderna e otimizando o compilador.

Quanto a máquinas bizarras … Se não houver nenhum módulo U congruente assinado UINT_MAX + 1 para o int não assinado, digamos que eu queira lançar uma exceção. Se houver mais de um (não tenho certeza de que isso seja possível), digamos que eu queira o maior.

OK, segunda tentativa:

 int unsigned_to_signed(unsigned n) { int int_n = static_cast(n); if (n == static_cast(int_n)) return int_n; // else do something long and complicated } 

Eu não me importo muito com a eficiência quando não estou em um sistema típico de dois pares, já que na minha modesta opinião isso é improvável. E se o meu código se tornar um gargalo nos onipresentes sistemas de magnitude de sinal de 2050, bem, aposto que alguém pode descobrir isso e otimizá-lo.

Agora, esta segunda tentativa é bem próxima do que eu quero. Embora a conversão para int seja definida pela implementação para algumas inputs, a conversão para unsigned é garantida pela norma para preservar o valor do módulo UINT_MAX + 1. Portanto, o condicional verifica exatamente o que eu quero e compila em nada em qualquer sistema que eu possa encontrar.

No entanto … ainda estou lançando para int sem primeiro verificar se ele irá invocar o comportamento definido pela implementação. Em algum sistema hipotético em 2050, ele poderia fazer quem sabe o quê. Então, digamos que eu queira evitar isso.

Pergunta: Como deve ser minha “terceira tentativa”?

Para recapitular, quero:

  • Transmitir de int não assinado para int assinado
  • Preserve o valor mod UINT_MAX + 1
  • Invocar apenas comportamento obrigatório
  • Compila em um não-op em uma máquina típica de dois complementos com otimização de compilador

[Atualizar]

Deixe-me dar um exemplo para mostrar por que essa não é uma questão trivial.

Considere uma implementação hipotética de C ++ com as seguintes propriedades:

  • sizeof(int) é igual a 4
  • sizeof(unsigned) é igual a 4
  • INT_MAX é igual a 32767
  • INT_MIN é igual a -2 32 + 32768
  • UINT_MAX é igual a 2 32 – 1
  • A aritmética no int é o módulo 2 32 (no intervalo INT_MIN até INT_MAX )
  • std::numeric_limits::is_modulo é verdadeiro
  • Casting unsigned n para int preserva o valor para 0 <= n <= 32767 e retorna zero caso contrário

Nesta implementação hipotética, existe exatamente um valor int congruente (mod UINT_MAX + 1) para cada valor unsigned . Então minha pergunta seria bem definida.

Eu afirmo que essa implementação hipotética de C ++ está totalmente de acordo com as especificações C ++ 98, C ++ 03 e C ++ 11. Eu admito que não memorizei todas as palavras de todas elas … Mas acredito que li atentamente as seções relevantes. Então, se você quiser que eu aceite sua resposta, você deve (a) citar uma especificação que exclui essa implementação hipotética ou (b) lidar com ela corretamente.

De fato, uma resposta correta deve lidar com todas as implementações hipotéticas permitidas pelo padrão. Isso é o que “invoca apenas o comportamento obrigatório” significa, por definição.

Incidentalmente, note que std::numeric_limits::is_modulo é totalmente inútil aqui por várias razões. Por um lado, isso pode ser true mesmo se os modelos não assinados para assinados não funcionarem para grandes valores não assinados. Por outro lado, pode ser true mesmo em sistemas de complemento ou de magnitude de sinal, se a aritmética for simplesmente o módulo inteiro. E assim por diante. Se sua resposta depende de is_modulo , está errado.

[Atualização 2]

A resposta do hvd me ensinou algo: Minha implementação hipotética de C ++ para inteiros não é permitida pelo C. moderno. Os padrões C99 e C11 são muito específicos sobre a representação de inteiros assinados; na verdade, eles só permitem dois-complemento, complemento de um e magnitude de sinal (seção 6.2.6.2 parágrafo (2);).

Mas C ++ não é C. Como se vê, esse fato está no cerne da minha pergunta.

O padrão original C ++ 98 foi baseado no muito mais antigo C89, que diz (seção 3.1.2.5):

Para cada um dos tipos inteiros assinados, há um tipo de inteiro não assinado correspondente (mas diferente) (designado com a palavra-chave não assinada) que usa a mesma quantidade de armazenamento (incluindo informações de sinal) e possui os mesmos requisitos de alinhamento. O intervalo de valores não-negativos de um tipo inteiro assinado é um sub-intervalo do tipo inteiro não assinado correspondente, e a representação do mesmo valor em cada tipo é a mesma.

C89 não diz nada sobre apenas ter um bit de sinal ou apenas permitir twos-complemento / complemento / sinal-magnitude.

O padrão C ++ 98 adotou esta linguagem quase literalmente (seção 3.9.1 parágrafo (3)):

Para cada um dos tipos inteiros assinados, existe um tipo de inteiro não assinado correspondente (mas diferente): ” unsigned char “, ” unsigned short int “, ” unsigned int ” e ” unsigned long int “, cada um dos quais ocupa o mesmo valor de armazenamento e tem os mesmos requisitos de alinhamento (3.9) que o tipo inteiro assinado assinado correspondente; ou seja, cada tipo inteiro assinado tem a mesma representação de object que seu tipo inteiro sem sinal correspondente. O intervalo de valores não-negativos de um tipo inteiro assinado é um sub-intervalo do tipo inteiro não assinado correspondente, e a representação do valor de cada tipo assinado / não assinado correspondente deve ser a mesma.

O padrão C ++ 03 utiliza linguagem essencialmente idêntica, assim como o C ++ 11.

Nenhuma especificação C ++ padrão restringe suas representações inteiras assinadas para qualquer especificação C, até onde eu saiba. E não há nada que obrigue um único bit de sinal ou algo do tipo. Tudo o que diz é que números inteiros assinados não negativos devem ser um sub-intervalo do não assinado correspondente.

Então, novamente eu reivindico que INT_MAX = 32767 com INT_MIN = -2 32 +32768 é permitido. Se a sua resposta assumir o contrário, é incorreto, a menos que você cite um padrão C ++ provando que estou errado.

    Expandindo na resposta de user71404:

     int f(unsigned x) { if (x <= INT_MAX) return static_cast(x); if (x >= INT_MIN) return static_cast(x - INT_MIN) + INT_MIN; throw x; // Or whatever else you like } 

    Se x >= INT_MIN (mantenha as regras de promoção em mente, INT_MIN é convertido em unsigned ), então x - INT_MIN <= INT_MAX , portanto, isso não terá nenhum estouro.

    Se isso não for óbvio, dê uma olhada na afirmação "Se x >= -4u , então x + 4 <= 3 ", E tenha em mente que INT_MAX será igual a pelo menos o valor matemático de -INT_MIN - 1 .

    Nos sistemas mais comuns, onde !(x <= INT_MAX) implica x >= INT_MIN , o otimizador deve poder (e no meu sistema, é capaz) remover a segunda verificação, determinar que as duas instruções de return possam ser compiladas para o mesmo código e remova o primeiro cheque também. Listagem de assembly gerada:

     __Z1fj: LFB6: .cfi_startproc movl 4(%esp), %eax ret .cfi_endproc 

    A implementação hipotética na sua pergunta:

    • INT_MAX é igual a 32767
    • INT_MIN é igual a -2 32 + 32768

    não é possível, por isso não precisa de consideração especial. INT_MIN será igual a -INT_MAX ou a -INT_MAX - 1 . Isso segue da representação de C de tipos inteiros (6.2.6.2), que requer n bits para serem bits de valor, um bit para ser um bit de sinal e permite apenas uma única representação de trap (não incluindo representações inválidas por causa de bits de preenchimento) , ou seja, aquele que de outra forma representaria zero negativo / -INT_MAX - 1 . C ++ não permite representações inteiras além do que C permite.

    Atualização : O compilador da Microsoft aparentemente não percebe que x > 10 e x >= 11 testam a mesma coisa. Apenas gera o código desejado se x >= INT_MIN é substituído por x > INT_MIN - 1u , o que pode detectar como a negação de x <= INT_MAX (nesta plataforma).

    [Atualização do questionador (Nemo), elaborando nossa discussão abaixo]

    Eu agora acredito que esta resposta funciona em todos os casos, mas por razões complicadas. É provável que eu recompense essa solução, mas quero capturar todos os detalhes, caso alguém se importe.

    Vamos começar com C ++ 11, seção 18.3.3:

    A Tabela 31 descreve o header .

    ...

    O conteúdo é o mesmo que o header da biblioteca C padrão .

    Aqui, "Padrão C" significa C99, cuja especificação restringe severamente a representação de números inteiros assinados. Eles são iguais a inteiros sem sinal, mas com um bit dedicado a "sign" e zero ou mais bits dedicados a "padding". Os bits de preenchimento não contribuem para o valor do inteiro, e o bit de sinal contribui apenas como complemento de dois, complemento de um ou magnitude de sinal.

    Como o C ++ 11 herda as macros de C99, INT_MIN é -INT_MAX ou -INT_MAX-1, e o código do hvd é garantido para funcionar. (Note que, devido ao preenchimento, INT_MAX poderia ser muito menor do que UINT_MAX / 2 ... Mas, graças ao modo como os assinados assinados-> não assinados funcionam, essa resposta trata bem.)

    C ++ 03 / C ++ 98 é mais complicado. Ele usa o mesmo texto para herdar de "Standard C", mas agora "Standard C" significa C89 / C90.

    Todos estes - C ++ 98, C ++ 03, C89 / C90 - tem o texto que eu dou na minha pergunta, mas também inclui isto (C ++ 03 seção 3.9.1 parágrafo 7):

    As representações de tipos integrais devem definir valores por meio de um sistema de numeração binária pura. (44) [ Exemplo : esta Norma permite o complemento de 2, o complemento de 1 e representações de magnitude assinada para tipos inteiros.]

    Nota de rodapé (44) define "sistema puro de numeração binária":

    Uma representação posicional para inteiros que usa os dígitos binários 0 e 1, nos quais os valores representados por bits sucessivos são aditivos, começam com 1 e são multiplicados pela potência integral sucessiva de 2, exceto talvez pelo bit com a posição mais alta.

    O interessante dessa redação é que ela se contradiz, porque a definição de "sistema puro de numeração binária" não permite uma representação de sinal / magnitude! Ele permite que o bit alto tenha, digamos, o valor -2 n-1 (complemento de dois) ou - (2 n-1 ) (complemento de um). Mas não há valor para o bit alto que resulta em sinal / magnitude.

    De qualquer forma, minha "implementação hipotética" não se qualifica como "binário puro" sob essa definição, portanto, isso é descartado.

    No entanto, o fato de o bit alto ser especial significa que podemos imaginar que ele contribui com qualquer valor: um valor positivo pequeno, um valor positivo enorme, um valor negativo pequeno ou um valor negativo enorme. (Se o bit de sinal pode contribuir - (2 n-1 -1), por que não - (2 n-1 -2)? Etc.)

    Então, vamos imaginar uma representação de número inteiro assinado que atribui um valor maluco ao bit "sinal".

    Um pequeno valor positivo para o bit de sinal resultaria em um intervalo positivo para int (possivelmente tão grande quanto unsigned ), e o código do hvd lida bem com isso.

    Um valor positivo enorme para o bit de sinal resultaria em um int maior que unsigned , o que é proibido.

    Um valor negativo enorme para o bit de sinal resultaria em int representando um intervalo não contíguo de valores, e outro texto nas regras de especificação eliminadas.

    Finalmente, que tal um bit de sinal que contribui com uma pequena quantidade negativa? Poderíamos ter um 1 no "bit de sinal" contribuir, digamos, -37 para o valor do int? Então INT_MAX seria (digamos) 2 31 -1 e INT_MIN seria -37?

    Isso resultaria em alguns números com duas representações ... Mas o complemento de uns dá duas representações a zero, e isso é permitido de acordo com o "Exemplo". Em nenhum lugar a especificação diz que zero é o único inteiro que pode ter duas representações. Então eu acho que essa nova hipotética é permitida pela especificação.

    De fato, qualquer valor negativo de -1 até -INT_MAX-1 parece ser permissível como um valor para o "bit de sinal", mas nada menor (para que o intervalo não seja contíguo). Em outras palavras, INT_MIN pode ser qualquer coisa de -INT_MAX-1 a -1.

    Agora, adivinha o que? Para a segunda conversão no código do hvd para evitar o comportamento definido pela implementação, precisamos apenas que o x - (unsigned)INT_MIN menor ou igual a INT_MAX . Acabamos de mostrar que INT_MIN é pelo menos -INT_MAX-1 . Obviamente, x é no máximo UINT_MAX . A conversão de um número negativo para não assinado é o mesmo que adicionar UINT_MAX+1 . Coloque tudo junto:

     x - (unsigned)INT_MIN <= INT_MAX 

    se e apenas se

     UINT_MAX - (INT_MIN + UINT_MAX + 1) <= INT_MAX -INT_MIN-1 <= INT_MAX -INT_MIN <= INT_MAX+1 INT_MIN >= -INT_MAX-1 

    Esse último é o que acabamos de mostrar, então mesmo nesse caso perverso, o código realmente funciona.

    Isso exaure todas as possibilidades, terminando assim este exercício extremamente acadêmico.

    Conclusão: Existe um comportamento seriamente sub-especificado para números inteiros assinados em C89 / C90 que foram herdados por C ++ 98 / C ++ 03. Ele é corrigido em C99 e o C ++ 11 herda indiretamente a correção incorporando de C99. Mas até mesmo o C ++ 11 mantém a formulação auto-contraditória da "representação binária pura" ...

    Este código depende apenas do comportamento, exigido pela especificação, portanto, o requisito (a) é facilmente satisfeito:

     int unsigned_to_signed(unsigned n) { int result = INT_MAX; if (n > INT_MAX && n < INT_MIN) throw runtime_error("no signed int for this number"); for (unsigned i = INT_MAX; i != n; --i) --result; return result; } 

    Não é tão fácil com a exigência (b). Este compila em um não-op com gcc 4.6.3 (-Os, -O2, -O3) e com clang 3.0 (-Os, -O, -O2, -O3). Intel 12.1.0 se recusa a otimizar isso. E eu não tenho informações sobre o Visual C.

    Você pode explicitamente dizer ao compilador o que você quer fazer:

     int unsigned_to_signed(unsigned n) { if (n > INT_MAX) { if (n <= UINT_MAX + INT_MIN) { throw "no result"; } return static_cast(n + INT_MIN) - (UINT_MAX + INT_MIN + 1); } else { return static_cast(n); } } 

    Compila com o gcc 4.7.2 para x86_64-linux ( g++ -O -S test.cpp ) para

     _Z18unsigned_to_signedj: movl %edi, %eax ret 

    Se x é a nossa input …

    Se x > INT_MAX , queremos encontrar uma constante k tal que 0 < x – k*INT_MAX < INT_MAX .

    Isso é fácil – unsigned int k = x / INT_MAX; . Então, deixe unsigned int x2 = x - k*INT_MAX;

    Podemos agora converter x2 para int com segurança. Vamos int x3 = static_cast(x2);

    Agora queremos subtrair algo como UINT_MAX - k * INT_MAX + 1 de x3 , se k > 0 .

    Agora, em um sistema de complemento de 2s, contanto que x > INT_MAX , isso funcione para:

     unsigned int k = x / INT_MAX; x -= k*INT_MAX; int r = int(x); r += k*INT_MAX; r -= UINT_MAX+1; 

    Note que UINT_MAX+1 é zero em C ++ garantido, a conversão para int era noop, e nós subtraímos k*INT_MAX então adicionamos de volta em “o mesmo valor”. Assim, um otimizador aceitável deve ser capaz de apagar toda essa tolice!

    Isso deixa o problema de x > INT_MAX ou não. Bem, criamos 2 ramificações, uma com x > INT_MAX e outra sem. Aquele sem um casting estreito, que o compilador otimiza para um noop. Aquele com … faz um noop depois que o otimizador é feito. O otimizador inteligente realiza os dois ramos para a mesma coisa e descarta o ramo.

    Problemas: se UINT_MAX for realmente grande em relação a INT_MAX , o acima pode não funcionar. Estou assumindo que k*INT_MAX <= UINT_MAX+1 implicitamente.

    Nós provavelmente poderíamos atacar isso com algumas enums como:

     enum { divisor = UINT_MAX/INT_MAX, remainder = UINT_MAX-divisor*INT_MAX }; 

    que funcionam em 2 e 1 em um sistema de complemento de 2s, eu acredito (estamos garantidos para que a matemática funcione? Isso é complicado ...), e faça lógica baseada neles que facilmente otimize em sistemas de complemento não-2s ...

    Isso também abre o caso de exceção. Isso só é possível se UINT_MAX for muito maior que (INT_MIN-INT_MAX), então você pode colocar seu código de exceção em um bloco if perguntando exatamente a questão de alguma forma, e isso não irá atrasá-lo em um sistema tradicional.

    Não sei exatamente como construir essas constantes de tempo de compilation para lidar corretamente com isso.

    Meu dinheiro está usando o memcpy. Qualquer compilador decente sabe otimizá-lo:

     #include  #include  #include  static inline int unsigned_to_signed(unsigned n) { int result; memcpy( &result, &n, sizeof(result)); return result; } int main(int argc, const char * argv[]) { unsigned int x = UINT_MAX - 1; int xx = unsigned_to_signed(x); return xx; } 

    Para mim (Xcode 8.3.2, Apple LLVM 8.1, -O3), isso produz:

     _main: ## @main Lfunc_begin0: .loc 1 21 0 ## /Users/Someone/main.c:21:0 .cfi_startproc ## BB#0: pushq %rbp Ltmp0: .cfi_def_cfa_offset 16 Ltmp1: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp2: .cfi_def_cfa_register %rbp ##DEBUG_VALUE: main:argc <- %EDI ##DEBUG_VALUE: main:argv <- %RSI Ltmp3: ##DEBUG_VALUE: main:x <- 2147483646 ##DEBUG_VALUE: main:xx <- 2147483646 .loc 1 24 5 prologue_end ## /Users/Someone/main.c:24:5 movl $-2, %eax popq %rbp retq Ltmp4: Lfunc_end0: .cfi_endproc 

    std::numeric_limits::is_modulo é uma constante de tempo de compilation. então você pode usá-lo para a especialização de modelos. problema resolvido, pelo menos se o compilador tocar junto com o inlining.

     #include  #include  #include  #ifdef TESTING_SF bool const testing_sf = true; #else bool const testing_sf = false; #endif // C++ "extensions" namespace cppx { using std::runtime_error; using std::string; inline bool hopefully( bool const c ) { return c; } inline bool throw_x( string const& s ) { throw runtime_error( s ); } } // namespace cppx // C++ "portability perversions" namespace cppp { using cppx::hopefully; using cppx::throw_x; using std::numeric_limits; namespace detail { template< bool isTwosComplement > int signed_from( unsigned const n ) { if( n <= unsigned( numeric_limits::max() ) ) { return static_cast( n ); } unsigned const u_max = unsigned( -1 ); unsigned const u_half = u_max/2 + 1; if( n == u_half ) { throw_x( "signed_from: unsupported value (negative max)" ); } int const i_quarter = static_cast( u_half/2 ); int const int_n1 = static_cast( n - u_half ); int const int_n2 = int_n1 - i_quarter; int const int_n3 = int_n2 - i_quarter; hopefully( n == static_cast( int_n3 ) ) || throw_x( "signed_from: range error" ); return int_n3; } template<> inline int signed_from( unsigned const n ) { return static_cast( n ); } } // namespace detail inline int signed_from( unsigned const n ) { bool const is_modulo = numeric_limits< int >::is_modulo; return detail::signed_from< is_modulo && !testing_sf >( n ); } } // namespace cppp #include  using namespace std; int main() { int const x = cppp::signed_from( -42u ); wcout << x << endl; } 

    EDIT : Corrigido o código para evitar possíveis interceptações em máquinas não-modulares int (apenas um é conhecido por existir, ou seja, as versões configuradas arcaicamente do Unisys Clearpath). Por simplicidade, isso é feito não suportando o valor -2 n -1, onde n é o número de bits do valor int , em tal máquina (isto é, no Clearpath). na prática, esse valor não será suportado pela máquina (isto é, com sinal e magnitude ou a representação do complemento de 1).

    Eu acho que o tipo int tem pelo menos dois bytes, então o INT_MIN e o INT_MAX podem mudar em diferentes plataformas.

    Tipos fundamentais

    ≤climits≥ header

    Isso é perfeitamente compatível com o padrão e será compilado para não funcionar no MSVC / gcc.

     int unsigned_to_signed(unsigned int n) { union UltimateCast { unsigned int In; int Out; } cast; cast.In = n; return cast.Out; } 

    Para o código de chamada como:

     volatile unsigned int i = 32167; int main() { return unsigned_to_signed( i ); } 

    Nós teremos esta saída de assembly (g ++ -O3 -S):

     __Z18unsigned_to_signedj: movl 4(%esp), %eax ret _main: pushl %ebp movl %esp, %ebp andl $-16, %esp call ___main movl _i, %eax leave ret .globl _i .data .align 4 _i: .long 32167 

    E declarando unsigned_to_signed() como rendimentos inline :

     _main: pushl %ebp movl %esp, %ebp andl $-16, %esp call ___main movl _i, %eax leave ret .globl _i .data .align 4 _i: .long 32167 

    Qual é o código bem legal.