Getting a incorrect voltage from a analog sensor

I'm trying to build a very simple thermometer using shift registers, 7-segment LEDs, and a LM35. The idea of the project is to learn more about shift registers and how to use them. What I've done so far is this mess:

It's very basic, 3 75HC595N powering 3 7-segment LEDs and a LM35. I'm using this code to control the LEDs and get the information from the sensor:

/**
 *  Digital Thermometer
 *
 *  A cool and simple digital thermometer using:
 *    - 3x 74HC595 shift registers
 *    - 3x Common anode 7-segment displays
 *    - 1x LM35 analog thermometer
 *    - 22x 1k resistors
 *
 *  @author Nathan Campos <nathanpc@dreamintech.net>
 *  @version 1.0
 */

/**
 *  LED Array Bits and pins.
 *           D
 *        ABCPDEFG
 *        11101111
 */

const int temp = A0;
const int data =  2;
const int latch = 3;
const int clock = 4;
const int clr =  -1;


/**
 *  Arduino setup.
 */
void setup() {
  Serial.begin(9600);
  pinMode(data, OUTPUT);
  pinMode(latch, OUTPUT);
  pinMode(clock, OUTPUT);

  if (clr != -1) {
    pinMode(clr, OUTPUT);
  }
}

/**
 *  Clear the Shift Register.
 */
void shift_clear() {
  if (clr != -1) {
    // The clear pin is set.
    digitalWrite(latch, LOW);

    digitalWrite(clr, LOW);
    digitalWrite(clr, HIGH);

    digitalWrite(latch, HIGH);
  } else {
    // shift all the zeros.
  }
}

/**
 *  Shift some data into the Shift Register.
 *
 *  @param shift1 Bytes to shift into the first shift register.
 *  @param shift2 Bytes to shift into the second shift register.
 *  @param shift3 Bytes to shift into the third shift register.
 */
void shift_write(byte shift1, byte shift2, byte shift3) {
  digitalWrite(latch, LOW);  // Pull LOW to start sending data.
  shiftOut(data, clock, LSBFIRST, shift3);
  shiftOut(data, clock, LSBFIRST, shift2);
  shiftOut(data, clock, LSBFIRST, shift1);
  digitalWrite(latch, HIGH); // Pull HIGH to stop sending data.
}

/**
 *  Get the bits to light a digit in the 7-segment display.
 *
 *  @param digit A numeric character.
 *  @param light_decimal Want to light the decimal character?
 *  @return The shift register byte to light a digit.
 */
byte light_digit(unsigned int digit, bool light_decimal) {
  byte light = B00000000;

  // Build the binary for the shift register.
  switch (digit) {
    case 0:
      light = B11101110;
      break;
    case 1:
      light = B01100000;
      break;
    case 2:
      light = B11001101;
      break;
    case 3:
      light = B11101001;
      break;
    case 4:
      light = B01100011;
      break;
    case 5:
      light = B10101011;
      break;
    case 6:
      light = B10101111;
      break;
    case 7:
      light = B11100000;
      break;
    case 8:
      light = B11101111;
      break;
    case 9:
      light = B11100011;
      break;
    default:
      // Looks like we should return a "E" of Error.
      light = B10001111;
      break;
  }

  if (light_decimal) {
    // Looks like we need some decimal action going.
    light = light | B00010000;
  }

  return light;
}

/**
 *  Get a digit at a specified position from a integer.
 *
 *  @param number The number to be divided.
 *  @param digit Which digit to be get.
 *  @return The digit.
 */
unsigned int get_digit(unsigned int number, unsigned int digit) {
  static int powers[] = { 1, 10, 100 };
  if (number <= 999) {
    return (number / powers[digit]) % 10;  // The digit.
  } else {
    return 10;  // Just so we'll get a Error digit.
  }
}

/**
 *  Light a 3 digits number.
 *
 *  @param number The number to be shown.
 */
void light_number(unsigned int number) {
  // Get each number.
  byte first = light_digit(get_digit(number, 2), false);
  byte second = light_digit(get_digit(number, 1), true);
  byte third = light_digit(get_digit(number, 0), false);

  // Shift the registers.
  shift_write(first, second, third);
}

/**
 *  Check for the temperature and return a integer for the LEDs.
 *
 *  @return Integer for the LEDs.
 */
unsigned int check_temperature() {
  delay(20);
  int reading = analogRead(temp);
  float voltage = reading * (5.0 / 1023);
  float celcius = (voltage - 0.5) * 100;

  Serial.println(voltage);

  //Serial.print(celcius);
  //Serial.println(" C");
  return celcius * 10;
}

/**
 *  Arduino main loop.
 */
void loop() {
  //check_temperature();
  light_number(check_temperature());
  delay(2000);
}

The problem is that the readings from the Arduino serial monitor are "incorrect" since the temperature of the room is ~23C:

0.85 – 0.74 – 0.73 – 0.78 – 0.80 – 0.72 – 0.71 – 0.81 – 0.61 – 0.62 – 0.71 – 0.81 – 0.79 – 0.69 – 0.74 – 0.78 – 0.80 – 0.77 – 0.74 – 0.78 – 0.80 – 0.71 – 0.67 – 0.71 – 0.67 – 0.71 – 0.67

When I measure the voltage between the Ground pin and the Output pin I get the correct output for the current temperature (0.23):

If I measured the voltage between the Ground and +Vs pin I get 3.84V:

Since this is a learning project I would love to know why this is happening and how to correct it. I think the problem might be related to the power that the LED array is using, if needed I can use a external 5V power supply for them and let the Arduino powering only with the sensor.