Converting decimal/integer to binary - how and why it works the way it does?

Question

As already asked David in a comment of an answer here, I'm really interested on how this function works, since I can't seem to get the same (correct) values if changing result length from 32 to 16 or 8.

I used function

function IntToBin(Value: LongWord): string;
var
  i: Integer;
begin
  SetLength(Result, 32);
  for i := 1 to 32 do begin
    if ((Value shl (i-1)) shr 31) = 0 then begin
      Result[i] := '0'
    end else begin
      Result[i] := '1';
    end;
  end;
end;

which somehow works just fine. (1 is returned as 000....001, 2 as 000....010, 3 as 000...011, etc...).

However, since I only needed 8 chars long string result, I changed the numbers in a function to 8 to get this:

function IntToBin(Value: LongWord): string;
var
  i: Integer;
begin
  SetLength(Result, 8);
  for i := 1 to 8 do begin
    if ((Value shl (i-1)) shr 7) = 0 then begin
      Result[i] := '0'
    end else begin
      Result[i] := '1';
    end;
  end;
end;

but I get results as they follow:

 1: 00000001
 2: 00000011
 3: 00000011
 4: 00000111
 5: 00000111
 6: 00000111
 7: 00000111
 8: 00001111
 9: 00001111
10: 00001111
11: 00001111
12: 00001111

Kinda same for 16 instead of 8.

Tried to change LongWord to Integer and Byte as well, but got the same results.

So... hm... what am I missing here, and don't understand? :/

PS: Asking in learning purposes, solved my case with Copy(Result, 25, 8) at the end of the first function, because needed 8 chars long string passed, but I really want to understand what's going on... :)

Thanks

Scottscotti

Answer 1

The left shift in the code is meant to shift the bit you are interested in to the very left hand edge of the data type. By doing so, all bits to the left are shifted off the end and lost. Then when you shift right again, we shift all the way to the other end. The result is either 0 or 1.

However, your data type is still 32 bits, and so you are not shifting far enough. You are not getting all the bits to the left of the target bit to fall off the end. And so they return when you shift to the right.

To make your code work you need this:

function IntToBinLowByte(Value: LongWord): string;
var
  i: Integer;
begin
  SetLength(Result, 8);
  for i := 1 to 8 do begin
    if ((Value shl (24+i-1)) shr 31) = 0 then begin
      Result[i] := '0'
    end else begin
      Result[i] := '1';
    end;
  end;
end;

A version that might be easier to understand, in relation to the original, would be like this:

function IntToBinLowByte(Value: LongWord): string;
var
  i: Integer;
begin
  SetLength(Result, 8);
  for i := 25 to 32 do begin
    if ((Value shl (i-1)) shr 31) = 0 then begin
      Result[i-24] := '0'
    end else begin
      Result[i-24] := '1';
    end;
  end;
end;

Frankly however it is better to operate on a single byte. And I find this double shifting to be a little obscure. I'd use a single shift and a bit mask. Like this:

function IntToBinByte(Value: Byte): string;
var
  i: Integer;
begin
  SetLength(Result, 8);
  for i := 1 to 8 do begin
    if (Value shr (8-i)) and 1 = 0 then begin
      Result[i] := '0'
    end else begin
      Result[i] := '1';
    end;
  end;
end;

And call it like this

str := IntToBinByte(Value and $ff);

assuming that Value is a 32 bit data type. Obviously if it is already a Byte then you don't need the bitwise and.

And the original 32 bit function would read better like this, in my humble opinion.

---

Earlier versions of this answer had the following incorrect attempt to solve the problem:

function IntToBinByte(Value: Byte): string;
var
  i: Integer;
begin
  SetLength(Result, 8);
  for i := 1 to 8 do begin
    if ((Value shl (i-1)) shr 7) = 0 then begin
      Result[i] := '0'
    end else begin
      Result[i] := '1';
    end;
  end;
end;

The problem is that, even though Value is an 8 bit type, the bitwise operations are performed in 32 bit registers. So the bits that are left shifted to bit number >7 return when the right shift is performed. You can fix this easily enough by masking out those bits that are meant to fall off the end. Like this:

function IntToBinByte(Value: Byte): string;
var
  i: Integer;
begin
  SetLength(Result, 8);
  for i := 1 to 8 do begin
    if (Value shl (i-1) and $ff) shr 7 = 0 then begin
      Result[i] := '0'
    end else begin
      Result[i] := '1';
    end;
  end;
end;

This code is really convoluted I don't recommend that anyone ever uses it. The best version, in my opinion, is the third block of code in my answer.

Pistachio

Ohh, ok. Now I think I understand more clearly what's going on. The second code works flawlessly. :) Thank you! Though, if I fully understand this, if I'd put Byte as type of value (what you already suggested in comments in the other thread), this then would be 8 bit, not 32, so therefore should work with shifting 0 left and 7 to the right, or it's not the same? – Scottscotti

Just saw that, yes. However, the third example doesn't work for me, even when calling it with "and $ff"... ? – Scottscotti

the fourth works, either if called with or without and $ff. Only the third one keeps feeding me with the same as I got in the first try (as posted in question). Bdw, thank you David, for you effort. :) – Scottscotti

Did you paste it verbatim. It is important that the shl is performed in a byte context. – Pistachio

Note that the and $ff is relevant if your value is greater than $ff. If you pass 15 and $ff then clearly the and does nothing. – Pistachio

You might be interested in this question: #21362955 – Pistachio

You're right, it looks interesting. Maybe just a little to advanced for me though.. :D But I'm glad I started such a debate. ;) – Scottscotti

If performance is critical, this routine could be used, function IntToBinByte( Value: Byte): String; var i: Integer; pStr: PChar; begin SetLength( Result,8); pStr := PChar(Pointer(Result)); for i := 7 downto 0 do begin pStr[i] := Char(Ord('0') + ((Value shr (7 - i)) and 1)); end; end; – Zacek

@LURD You should rather post this as another possible answer, to have it all there. – Scottscotti

Answer 2

As David so clearly answered, your bitshifting was either too short, or the operand was implicitly expanded by the compiler.

If performance is important, here is a routine that is faster than the one David presented:

function IntToBinByte(Value: Byte): String; 
var 
  i: Integer; 
  pStr: PChar; 
begin 
  SetLength(Result, 8); 
  pStr := PChar(Pointer(Result));  // Get a pointer to the string
  for i := 7 downto 0 do begin 
    pStr[i] := Char(Ord('0') + ((Value shr (7 - i)) and 1)); 
  end; 
end;

By working with a pointer, you avoid protecting the string every time it is updated. The protection is not needed here, since no other part of your program can access the Result string.

The string protection scheme in Delphi is called "Copy On Write" (COW), and works by having a reference counter that keeps count on every instance that is referencing the string. When a string is written on and the reference count is greater than 1, a new string is allocated for writing.

Zacek

So with your example the copy of a string (or copies? does it copy just each time the whole, or everytime until done?) aren't created and therefore it goes on faster. I see. Might come handy for heavier operations and projects.. :) thanks. – Scottscotti

My routine avoids the built in reference count checking mechanism, which has an overhead, this is the reason why it is faster. The way Davids function works, there is still no copying taking place, because there is only one holding a reference to the string. – Zacek

Answer 3

Personally, I'd do it this way:

function inttobin (p_nb_int: uint64; p_nb_digits: byte=64): string;
begin
  SetLength(Result, p_nb_digits);
  while p_nb_digits > 0 do
  begin
    if odd(p_nb_int) then
      Result[p_nb_digits] := '1'
    else
      Result[p_nb_digits] := '0';
    p_nb_int := p_nb_int shr 1;
    dec(p_nb_digits);
  end;
end;

Tobolsk

This looks far more complicated to me. (focused on "to me"...). Also, I need to pass length separately, so it requires special attention and extra data each time, if using for different types... :) Thanks for the hint and another option & opinion, though! :) – Scottscotti

The answer also doesn't really address the question that was asked. Of course, it's more flexible being able to work with any length data type in one function. I'd certainly make p_nb_digits be of type Integer, the native integer type. No benefit at all of using byte here. – Pistachio

This approach use the same approach as the third block of code in my answer. The downside of the way it is done here is that it modifies an actual input parameter which is best avoided if possible. Another downside is that the compiler appears not to optimise p_nb_int into a register. This code results in a lot of mov instructions just to perform p_nb_int := p_nb_int shr 1; The optimiser is able to remove all of them using the approach in the question, and the various methods outlined in my answer. Probably performance is not key here, but it still an interesting point I think. – Pistachio

Answer 4

function TForm1.Dec2Bin(iDec: Integer): string;
begin
  Result:='';
while iDec>0 do
  begin
    Result:=IntToStr(iDec and 1)+Result;
    iDec:=iDec shr 1;
  end;
end;

Wentworth

please add an explanation. – Sphinx

Answer 5

function IntToBin2(Value: Integer): string;
var
  i, pol: Integer;
begin
  Result:= '';
  for i := 1 to Value do
  begin
    pol:= Value div 2;
    Result:= IntToStr(Value - pol * 2) + Result;
    Value:= pol;
    if pol = 0 then
      Break;
  end;
end;

Donatello

Could you give at least a small explanation of what your code is doing? – Excess

Answer 6

had to write this for my South African IT Grade 12 Final Examinations 2020 Exam. it was in a GUI app, for this example i used a console app.

program IntToBinary;
    
    {$APPTYPE CONSOLE}
    
    {$R *.res}
    
    uses
      System.SysUtils,StrUtils;
    
    var
    i,iNumber,iReminder:integer;
    sTemp:string;
    sBinary:string;
    begin
      try
        { TODO -oUser -cConsole Main : Insert code here }
          Writeln('Enter integer number:');
          Readln(Input,iNumber);
          sTemp:= '';
          repeat
          iNumber := iNumber DIV 2;
          iReminder:= iNumber MOD 2;
          sTemp:= sTemp+' '+inttostr(iReminder);
          until (iNumber = 0);
    
          sBinary:= AnsiReverseString(sTemp);
          Writeln(sBinary);
          readln;
    
      except
        on E: Exception do
          Writeln(E.ClassName, ': ', E.Message);
      end;
    end.

Dislimn