Representação de inteiros não negativos

• representação posicional
  • base b: necessidade de b dígitos
  • uso de letras quando base maior que 10
• tamanho da base X tamanho da representação
  • desconforto de trabalhar com base muito pequena
  • uso da base 16 (hexadecimal) comum em software básico: mapeamento direto para base 2
• conversão entre bases
  • base b para base 10: uso direto da definição da representação posicional
  • base 10 para base b: uso de divisões sucessivas e relação com representação posicional (definição de divisão)

Representação de dados básicos em um computador

inteiros não negativos

• uso de 1, 2, 4 ou ... bytes para representar o número na base 2
• representações big-endian (na memória, byte mais significativo tem endereço mais baixo) e little-endian (na memória, byte mais significativo tem endereço mais alto)
• do ponto de vista do programa C, para enxergar se a máquina é big-endian ou little-endian é necessário "quebrar" o sistema de tipos. Por exemplo:

  #include <stdio.h>
  
  typedef unsigned char *byte_ptr;
  
  void mostra (byte_ptr inicio, int tam) {
    int i;
    for (i=0;i<tam;i++)
      printf("%.2x", inicio[i]);
    printf("\n");
  }
  
  void mostra_int (int num) {
    mostra((byte_ptr) &num, sizeof(int));
  }
  
  

• limitações de representação:
  • com 1 byte podemos representar inteiros não negativos de 0 a 255
  • com 2 bytes podemos representar inteiros não negativos de 0 a 65.535
  • com 4 bytes ...
• lembrar que essas limitações também valem para endereços, ou seja:
  • com 2 bytes só podemos expressar endereços de 0 a 65.535, ou seja, só podemos endereçar 64Kbytes de memória
  • com 4 bytes podemos endereçar 4 Giga bytes de memória...
• definições do ANSI C:
  • char: 1 byte
  • short int: pelo menos 2 bytes (16 bits)
  • int: pelo menos 2 bytes (16 bits)
  • long int: pelo menos 4 bytes (32 bits)
  • ... e representação de long int tem que ocupar pelo menos tantos bytes quanto a de int que tem que ocupar pelo menos tantos bytes como a de short int...

caracteres

• uso de uma tabela para mapear inteiros não negativos em símbolos que chamamos de caracteres
• sempre lembrando que na memória não há registro do que está sendo representado!
• tabela mais comum: ASCII
• em C: o tipo char define apenas um inteiro pequeno (1 byte); podemos manipular um char exatamente como um int.
• em particular, podemos fazer coisas como:

  char c;
  int val;
  ...
  if (c>'0') ...
  ...
  val = c-'0';
  ...
  val = c-'a'+10;
  ...
  

• NÃO, E, OU, OU EXCLUSIVO: ~, &, |, ^

     int a, b, c;
  
     a = 0xFF00;
     b = 0x00FF;
  
     c = a | b;	/* c = 0xFFFF */
     ...
     

   int a, b, c;

   a = 0xF;
   b = ;

   c = a << 4;	/* c = 0xF0 */
   ...
   

Referência

• CS:APP, 2.2.1, 2.1.8, 2.1.9, 2.1.10.

Representação de tipos estruturados

Arrays

Alocação de arrays simples

• alocação contígua na memória
• primeiro elemento (índice 0 em C) corresponde ao menor endereço de memória
• espaço ocupado por um array de declaração tipo nome[tam]: sizeof(tipo)*tam bytes

  char A[12];
  char *B[12];
  int C[12];
  double D[12];
  double *E[12];
  
  Array       tamanho de elemento     tam. total    end. inicial    end. elem i
    A                           1             12               x            x+i
    B                           4             48               x           x+4i
    C                           4             48               x           x+4i
    D                           8             96               x           x+8i
    E                           4             48               x           x+4i
  

Relação entre ponteiros e arrays em C

• depois de uma declaração de array em C, o nome dado ao array equivale a um ponteiro (cujo valor não pode ser alterado...)
  • ou seja, depois da declaração int a[TAM], podemos encarar a como um ponteiro constante do tipo int*
• o valor de uma variável decalarada como array é o endereço inicial desse array na memória
  • ou seja, dado int a[10], a equivale a &a[0]!
  • por isso, quando passamos um nome de array como parâmetro, estamos sempre passando o endereço do array!

Aritmética Básica com Ponteiros

• o resultado da expressão (pa + i), onde pa é um ponteiro e i um inteiro, depende da declaração de pa
• dada a declaração tipo *pa, (pa + i) equivale a pa + sizeof(tipo)*i
  • por exemplo, se declararmos int *pi e em algum ponto do escopo dessa declaração fizermos pi+3, estaremos na realidade somando 3*sizeof(int) (12 no nosso compilador) ao valor de pi!
  • aproveitando..
    • qual a diferença entre pa++ e ++pa?
    • qual a diferença entre p++ e (*p)++?
  • e o que faz *p++?

Outras Observações

• Dois ponteiros podem ser comparados se p1 e p2 apontam para o mesmo tipo
  • p1 == p2 se apontam para o mesmo elemento
  • p1 maior que p2 se o endereço contido em p2 é inferior ao contido em p1
• Na subtração, p1 - p2 fornece o número de elementos entre p2 e p1, e não o número de bytes.
• Com aritmética de ponteiros e a equivalência entre arrays e ponteiros, dadas as declarações int a[5]; int *p = a, temos que

  p[3] <=> *(p+3) <=> a[3] <=> *(a+3)
  

• Dada a declaração tipo nome[tam], cálculo do endereço de memória do elemento a[i]:
  • em C: a + i
  • em bytes: a + sizeof(tipo)*i
• existência do ponteiro NULL, igual a 0

Arrays multi-dimensionais

• em C: int a[3][2] declara uma array de três posições onde cada posição é um array de duas posições
  • ou seja, a[i] é um array (um ponteiro)
• em quase todas as linguagens, independentemente do uso de arrays de arrays, os arrays bidimensionais são armazenados por linhas (row-major order) na memória, ie, a declaração char a[2,3] gera na memória: a[0,0], a[0,1], a[0,2], a[1,0], ...
• dada a declaração tipo nome[tam1][tam2], cálculo do endereço de memória do elemento a[i][j]:
  • em C: a + tam2*i +j
  • em bytes: a + tam2*sizeof(tipo)*i + sizeof(tipo)*j

Arrays como parâmetros formais

• Quando declaramos um parâmetro formal de um função C que é um array unidimensional, não precisamos declarar seu tamanho. Por que?
• Tanto faz declararmos um parâmetro formal como um array de inteiros ou como um ponteiro para inteiros. Por que?
• Se o parâmetro for um array bidimensional, teremos que declarar pelo menos o número de "colunas". Por que?

Referência

• CS:APP, 3.8, 3.11 (por enquanto ignorando a parte de código assembly).

• referência: C Programming Notes. Steve Summit.