Biến bit là O (1) hoặc O (n)?

Question

Hoạt động chuyển dịch O(1) hoặc O(n)?

Có nghĩa là máy tính thường yêu cầu nhiều hoạt động hơn để thay đổi 31 địa điểm thay vì chuyển 1 địa điểm?

Hoặc điều đó có nghĩa là số hoạt động cần thiết để dịch chuyển là hằng số bất kể chúng ta cần thay đổi bao nhiêu điểm?

PS: tự hỏi nếu phần cứng là một từ khóa thích hợp ..

Answer 1

Một số tập lệnh được giới hạn ở một ca trên bit cho mỗi lệnh.Và một số bộ hướng dẫn cho phép bạn chỉ định bất kỳ số bit nào để dịch chuyển trong một lệnh, thường mất một chu kỳ đồng hồ trên các bộ vi xử lý hiện đại (hiện đại là một từ cố ý mơ hồ). Xem dan04's answer về bộ phận đóng thùng, một mạch dịch chuyển nhiều hơn một bit trong một thao tác.

Tất cả đều tóm tắt thuật toán logic. Mỗi bit trong kết quả là một hàm logic dựa trên đầu vào. Đối với một sự thay đổi đúng, thuật toán sẽ giống như sau:

• Nếu lệnh là [shift right] và bit 1 của đầu vào là 1, thì bit 0 của kết quả là 1, bit khác 0 là 0 .
• Nếu hướng dẫn là [shift right], sau đó cắn 1 = 2. chút
• , vv

Nhưng phương trình logic có thể chỉ là một cách dễ dàng là:

• Nếu lệnh là [shift phải] và toán hạng là 1, thì bit kết quả là 0 = bit đầu vào được chuyển 1.
• nếu số lượng là 2 thì bit 0 = bit 2.
• v.v.

Các cổng logic, không đồng bộ, có thể thực hiện tất cả điều này trong một chu kỳ đồng hồ. Tuy nhiên, đúng là sự thay đổi duy nhất cho phép chu kỳ đồng hồ nhanh hơn và ít cổng hơn để giải quyết, nếu tất cả những gì bạn đang so sánh là hai hương vị của một hướng dẫn. Hoặc thay thế là làm cho nó mất nhiều thời gian để giải quyết, do đó, các hướng dẫn có 2 hoặc 3 đồng hồ hoặc bất cứ điều gì, và logic đếm đến 3 sau đó chốt kết quả.

Ví dụ: MSP430 chỉ có hướng dẫn xoay đúng một bit (vì bạn có thể thực hiện một lần dịch chuyển đơn hoặc xoay sang trái với hướng dẫn khác, mà tôi sẽ để người đọc tìm ra).

Bộ lệnh ARM cho phép xoay vòng nhiều bit ngay lập tức và đăng ký dựa trên, thay đổi số học và thay đổi lôgic. Tôi nghĩ rằng chỉ có một hướng dẫn xoay thực tế và khác là một bí danh, bởi vì xoay trái 1 là giống như một xoay phải 32, bạn chỉ cần một shifter một hướng thùng để thực hiện một xoay nhiều bit.

SHL trong x86 cho phép nhiều hơn một bit cho mỗi lệnh, nhưng nó được sử dụng để có nhiều hơn một đồng hồ.

v.v., bạn có thể dễ dàng kiểm tra bất kỳ hướng dẫn nào được đặt ra ở đó.

Câu trả lời cho câu hỏi của bạn là câu hỏi chưa được khắc phục. Đôi khi nó là một hoạt động, một chu kỳ, một hướng dẫn. Đôi khi nó là một hướng dẫn nhiều chu kỳ đồng hồ. Đôi khi nó là nhiều hướng dẫn, nhiều chu kỳ đồng hồ.

Trình biên dịch thường tối ưu hóa cho những thứ này. Giả sử bạn có một bộ hướng dẫn đăng ký 16 bit với lệnh hoán đổi byte và lệnh AND có ngay lập tức, nhưng chỉ có một thay đổi bit. Bạn có thể nghĩ rằng dịch chuyển 8 bit sẽ yêu cầu 8 chu kỳ lệnh thay đổi, nhưng bạn chỉ có thể hoán đổi byte (một lệnh) và sau đó AND nửa dưới thành 0 (có thể có hai hướng dẫn, hoặc có thể là chỉ dẫn chiều dài từ thay đổi của hai từ, hoặc nó có thể mã hóa thành một lệnh duy nhất) vì vậy nó chỉ mất 2 hoặc 3 lệnh/chu kỳ đồng hồ thay vì 8. Cho một sự thay đổi 9 bit, bạn có thể làm điều tương tự và thêm một ca, làm cho nó 9 đồng hồ so với 3 hoặc 4 Ngoài ra, trên một số kiến ​​trúc, nó nhanh hơn để nhân 256 hơn để thay đổi bởi 8, vv, vv Mỗi tập lệnh có những hạn chế và thủ thuật riêng của nó.

Thậm chí không phải là trường hợp hầu hết các bộ lệnh cung cấp nhiều bit hoặc giới hạn nhất cho một bit. Các bộ xử lý nằm trong danh mục "máy tính", như X86, ARM, PowerPC và MIPS, sẽ dựa vào một hoạt động để dịch chuyển. Mở rộng cho tất cả các bộ vi xử lý nhưng không nhất thiết là "máy tính" thường được sử dụng ngày nay, và nó thay đổi theo cách khác, tôi sẽ nói nhiều hơn là một chút so với nhiều bit, vì vậy cần phải thực hiện nhiều thao tác để thực hiện thay đổi nhiều bit.

Answer 2

Bit chuyển là O (1) trên thực tế tất cả các bộ vi xử lý hiện hành.

Hãy xem, ví dụ: tại lệnh x86 "thu nhỏ". Toán hạng đầu tiên (trong cú pháp AT & T) là số bit cần dịch chuyển. Làm thế nào một trình biên dịch thực hiện chuyển dịch phụ thuộc vào trình biên dịch, nhưng nó sẽ là ngớ ngẩn để đặt thay đổi trong một vòng lặp khi một bộ xử lý có thể thay đổi N bit trong một lần.

Hợp đồng bổ sung: Re: "Chúng có yêu cầu nhiều thao tác dịch chuyển sang trái 31 hơn không?" Có nhiều loại thay đổi khác nhau (nếu bạn đang tự hỏi tại sao, hãy xem xét việc phải làm gì với các bit được chuyển ra khỏi thanh ghi), nhưng hầu hết các bộ vi xử lý có thể thực hiện chuyển đổi một lệnh với nhiều bit như GPR có thể lưu trữ. Để thực hiện phép dịch 40 bit trên thanh ghi 32 bit, yêu cầu chuyển qua nhiều thanh ghi (điều này giả định số 64 bit được lưu trữ trên 2 thanh ghi 32 bit), trên mỗi bộ xử lý tôi biết sẽ yêu cầu thêm hướng dẫn. Nó vẫn sẽ là O (1), có lẽ không phải là 1 đồng hồ. Là một lưu ý thú vị, bộ vi xử lý Pentium IV có tốc độ chậm thay đổi đáng kinh ngạc. Điều này thật mỉa mai bởi vì Intel đã đề xuất tối ưu hóa lịch sử^2 chia và nhân bằng cách dịch chuyển bit. Xem: this PDF và Google để biết thêm thông tin nếu quan tâm.

Answer 3

Đối với phần cứng thông thường, thanh ghi kích thước cố định, nó không đổi bất kể bạn thay đổi bao nhiêu chỗ.

Cũng lưu ý rằng việc sử dụng các ký hiệu O là khá kỳ lạ ở đây, bạn thường sẽ sử dụng nó để biểu thị mức độ phức tạp thuật toán dựa trên số lượng chuyển không phải là số nơi để chuyển ..

Answer 4

Một barrel shifter cho phép thay đổi được thực hiện trong O(log n) vượt qua — có thể được thực hiện trong cùng một chu kỳ đồng hồ, làm cho dịch chuyển hoạt động O(1).

Answer 5

Ahem, đã kiểm tra sự tò mò trong C# và nhận được kết quả hài hước.

var sw = Stopwatch.StartNew(); 
long l = 1; 
for (long i = 0; i < 20000000; i++) { 
    l = l << 60; l = l >> 60; 
    l = l << 60; l = l >> 60; 
    l = l << 60; l = l >> 60; 
    //... 
    // 50 of ^them^ total 

} 
Console.WriteLine(l + " " + sw.Elapsed); 

Mất 1,2 giây trên máy tính của tôi. Nhưng nếu tôi thay

l = l << 60; l = l >> 60; 

với

l = l << 1; l = l >> 1; 

thì thời gian tăng-2,0 giây. Không biết loại hình tối ưu nào đang được chơi ở đây, nhưng có vẻ lạ.

Answer 6

Như đã lưu ý, bộ dịch chuyển thùng có thể dịch chuyển một toán hạng một khoảng cách tùy ý trong thời gian không đổi. Một shifter thùng, tuy nhiên, tiêu thụ một số tiền hợp lý của không gian trên một CPU chết, vì vậy chúng không được bao gồm trong tất cả các thiết kế CPU.

Chỉ cho một ví dụ khá nổi tiếng, Intel Pentium III bao gồm bộ chuyển đổi thùng - nhưng Pentium IV đã làm không. Mã viết cho một Pentium III giả sử một thùng shifter đã có mặt đôi khi chậm lại khá nhiều trên một Pentium IV. Tôi đã có một số mã mã hóa (bao gồm nhiều chuyển dịch và quay) chạy nhanh hơn khoảng 4 lần trên một Pentium III 1,2 GHz so với trên Pentium IV 2,8 GHz.