Challenge: Tìm số lớn nhất trong 5 số nguyên

#42

Có imul không hay đâu, set bit thôi :slight_smile:

#43

5 số có là gì đâu mà phải dùng mảng hả bác :v

#44

né imul cũng được nè:

thay vì tìm k = c < 0, l = 0 hoặc 1, thì bây giờ tìm k = -(c < 0), nghĩa là tìm k = 0 hoặc -1, chuyển k về unsigned rồi xài k&c thay vì k*c:

int f3(int a, int b)
{
    int c = a - b;
    //unsigned int k = (unsigned int)(-(c < 0));
    int k = c >> 31;
    return a - (k & c);
}

assembly ra

f3(int, int):
        mov     edx, edi
        sub     edx, esi
        mov     eax, edx
        sar     eax, 31
        and     eax, edx
        sub     edi, eax
        mov     eax, edi
        ret

sar là shift left có dấu thay cho shr là shift left ko dấu => cho ra 0xffffffff thay cho 0x00000001.
imul eax, edx được thay thế bằng and eax, edx, né được imul.

3 Likes
#45

Bổ sung: Right (Arithmetic) Shift có dấu có tính chất x >> n == x / 2^n, vì vậy phải giữ bit dấu.

Nhắc lại dạng chính tắc của 1 số nguyên n bit bù 2 s:

s = -2^n * s[n-1] + 2^(n-2) * s[n-2] + … + 2s[1] + s[0]
vậy s/2^p = -2^(n-p) * s[n-1] + 2^(n-p-2) * s[n-2] + … + 2s[p+1] + s[p]
Để viết lại cho đúng dạng thì phải nhìn vào số mũ.
-2^(n-p) = -2^(n-p+1) + 2^(n-p)
-2^(n-p+1) = -2^(n-p+2) + 2^(n-p+1)
…
-2^(n-1) = -2^n + 2^(n-1)

2 Likes
#46

Lâu lắm mới thấy topic trong DNH đi sâu thế này
p/s: nhớ hồi implement phép toán cho các số ngàn bit

#47

Số unsigned thì có như vậy không ạ?

#48

Có chứ bạn. Nhưng left-shift có dấu là non-portable nên chỉ làm bit-trick với số không dấu.

1 Like
#49

Góp tí gạch, mình lập topic mà chả cmt code được 1 lần :smile:

Code Pascal, không dùng if, tuy vậy vi phạm yêu cầu cuối cùng: Không được dùng mảng. Mà nếu không dùng mảng thì khó code lắm, vì Pascal có kiểu boolean và kiểu số nguyên riêng biệt. Dù sao mình cũng up code lên vì code có hàm max xử lí 3 số liền 1 lúc, cuối cùng chỉ cần gọi hàm 2 lần.

Sửa code vì mình tìm được hàm chuyển bool -> string, rồi mình viết tay từ string -> int (khá dễ). Khỏi phải khai báo

const conv_bool: array[False..True] of integer = (0, 1);

đỡ vi phạm quy tắc :smile:

New code:

uses SysUtils;
var a, b, c, d, e: longint;

function BoolToInt(bool: boolean): longint;
var res: string;
begin
	// `tên_hàm := giá_trị` tương đương với `return giá_trị` ở các ngôn ngữ khác.
	res := BoolToStr(bool, '1', '0');
	BoolToInt := ord(res[1]) - 48;
end;

function max3(a, b, c: longint): longint;
begin
	max3 := BoolToInt(((a = b) and (b = c))) * a + 
	        BoolToInt(((a = b) and (b > c))) * b + 
	        BoolToInt(((b = c) and (c > a))) * c +
	        BoolToInt(((c = a) and (a > b))) * a +

	        BoolToInt(((a > b) and (a > c))) * a + 
	        BoolToInt(((b > a) and (b > c))) * b + 
	        BoolToInt(((c > a) and (c > b))) * c;
end;

begin
	readln(a, b, c, d, e);
	writeln(max3(max3(a, b, c), d, e));
end.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?