Xem mã nguồn của Logarit nhị phân

[[Tập tin:Binary logarithm plot with ticks.svg|thumbnail|right|upright=1.35|Đồ thị của {{math|log<sub>2</sub>{{Hair space}}''x''}} dưới dạng là hàm của một số thực dương {{mvar|x}}]]

Trong [[toán học]], '''logarit nhị phân''' ({{math|log<sub>2</sub>{{Hair space}}''n''}}) là [[lũy thừa]] mà số {{Math|2}} cần phải được nâng lên để được số {{Math|''n''}}, nghĩa là với mọi số thực {{Math|''x''}} thì
:<math>x=\log_2 n \quad\Longleftrightarrow\quad 2^x=n.</math>

Ví dụ, logarit nhị phân của {{Math|1}} là {{Math|0}}, logarit nhị phân của {{Math|2}} là {{Math|1}}, logarit nhị phân của {{Math|4}} là {{Math|2}} và logarit nhị phân của {{Math|32}} là {{Math|5}}.

Logarit nhị phân là [[logarit]] cơ số 2. Hàm logarit nhị phân là [[hàm ngược]] của hàm [[lũy thừa của 2]]. Cùng với {{math|log<sub>2</sub>}}, logarit nhị phân còn được ký hiệu là {{math|lg}}, {{math|ld}}, {{math|lb}} hoặc {{math|log}}.

Trong lịch sử, ứng dụng đầu tiên của logarit nhị phân nằm trong [[lý thuyết âm nhạc]] do [[Leonhard Euler]] tìm ra: logarit nhị phân của tỉ lệ tần số giữa hai [[tông nhạc]] cho biết số [[quãng tám]] nằm giữa hai tông đó. Logarit nhị phân có thể được dùng để tính độ dài của một số khi được biểu diễn trong [[hệ nhị phân]], hoặc số [[bit]] cần để mã hóa một thông điệp nào đó trong [[lý thuyết thông tin]]. Trong [[khoa học máy tính]], nó đếm số bước cần để thực thi thuật toán [[tìm kiếm nhị phân]] và các thuật toán có liên quan khác. Logarit nhị phân cũng có nhiều ứng dụng trong một số lĩnh vực như [[toán học tổ hợp]], [[tin sinh học]], [[nhiếp ảnh]] và trong thiết kế các [[giải đấu]] thể thao.

Logarit nhị phân là một trong các hàm toán học chuẩn của ngôn ngữ [[C (ngôn ngữ lập trình)|C]] và có trong một số bộ chương trình phần mềm toán học khác. Phần nguyên của logarit nhị phân có thể được tìm qua phép toán [[tìm bit 1 đầu tiên]] trên một giá trị nguyên hoặc tìm số mũ của một giá trị [[Số thực dấu phẩy động|dấu phẩy động]], trong khi phần thập phân có thể tính được một cách hiệu quả.<!-- "calculated efficiently" có phải là thuật ngữ chuyên ngành?  -->

== Lịch sử ==
{{Chính|Lịch sử logarit}}
[[Tập tin:Leonhard Euler.jpg|nhỏ|upright=0.75|[[Leonhard Euler]] là người đầu tiên ứng dụng logarit nhị phân vào [[lý thuyết âm nhạc]] năm 1739.]]
[[Lũy thừa của 2]] đã được biết đến từ thời cổ xưa; chẳng hạn, chúng xuất hiện trong [[Cơ sở (Euclid)|bộ ''Cơ sở'' của Euclid]], mệnh đề IX.32 (về [[Phân tích nhân tử|phân tích]] lũy thừa của 2) và IX.36 (một nửa [[định lý Euclid–Euler]] về sự xây dựng các [[số hoàn thiện]] chẵn), và logarit nhị phân chính là vị trí của chúng trong dãy lũy thừa của 2 được sắp xếp. Trên cơ sở đó, [[Michael Stifel]] được cho là đã xuất bản bảng logarit nhị phân đầu tiên vào năm 1544. Cuốn ''Arithmetica Integra'' của ông có một vài bảng số gồm các [[số nguyên]] và lũy thừa của 2 tương ứng. Khi đảo ngược các hàng trong các bảng số này thì chúng có thể được xem là bảng logarit nhị phân.<ref>{{Citation|title=Precalculus mathematics|first1=Vivian Shaw|last1=Groza|first2=Susanne M.|last2=Shelley|publisher=Holt, Rinehart and Winston|location=New York|year=1972|isbn=978-0-03-077670-0|page=182|url=https://books.google.com/books?id=yM_lSq1eJv8C&pg=PA182}}</ref><ref>{{citation|last=Stifel|first=Michael|author-link=Michael Stifel|language=la|page=31|title=Arithmetica integra|url=https://books.google.com/books?id=fndPsRv08R0C&pg=PA22|year=1544}}. Một bảng tương tự khác gồm 9 số xuất hiện ở tr. 237, và một bảng khác nữa ở tr. 249b được mở rộng sang lũy thừa âm.</ref>

Trước Stifel, nhà toán học [[Kỳ Na giáo|Kỳ Na]] thế kỷ 8 [[Virasena]] được cho là đã tìm ra tiền thân của logarit nhị phân. Khái niệm ''ardhachena'' của Virasena được xác định là số lần một số cho trước có thể chia hết cho 2. Định nghĩa này làm nảy sinh khái niệm về một hàm số cho cùng giá trị với logarit nhị phân đối với lũy thừa của 2,<ref>{{citation|page=[https://books.google.com/books?id=ymud91nTc9YC&pg=PA352 352]|title=The Crest of the Peacock: Non-European Roots of Mathematics|first=G. G.|last=Joseph|edition=3 |publisher=Princeton University Press|year=2011|isbn=978-0-691-13526-7}}.</ref> nhưng với các số nguyên khác thì hàm này cho biết [[Cấp p-adic|cấp 2-adic]] của số đó thay vì logarit.<ref>Chẳng hạn xem {{citation|title=Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness|volume=22|series=Progress in Computer Science and Applied Logic|first=Igor|last=Shparlinski|publisher=Birkhäuser|year=2013|isbn=978-3-0348-8037-4|page=35|url=https://books.google.com/books?id=z635BwAAQBAJ&pg=PA35}}.</ref>

Dạng hiện đại của logarit nhị phân, áp dụng cho bất kỳ số nào (không chỉ có lũy thừa của 2) do [[Leonhard Euler]] phát hiện vào năm 1739. Euler cũng là người đầu tiên tìm ra ứng dụng của logarit nhị phân trong lý thuyết âm nhạc, từ lâu trước khi người ta được biết ứng dụng của chúng trong lý thuyết thông tin và khoa học máy tính. Trong công trình của mình, Euler đã lập được bảng logarit nhị phân của các số nguyên từ 1 đến 8 chính xác đến 7 chữ số thập phân.<ref>{{citation|last=Euler|first=Leonhard|author-link=Leonhard Euler|contribution=Chapter VII. De Variorum Intervallorum Receptis Appelationibus|language=la|pages=102–112|publisher=Viện Hàn lâm Khoa học Saint Petersburg|title=Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae|url=https://scholarlycommons.pacific.edu/cgi/viewcontent.cgi?article=1032&context=euler-works|year=1739}}.</ref><ref>{{citation|title=London encyclopaedia; or, Universal dictionary of science, art, literature and practical mechanics: comprising a popular view of the present state of knowledge, Volume 4|first=Thomas|last=Tegg|year=1829|contribution=Binary logarithms|pages=142–143|url=https://books.google.com/books?id=E-ZTAAAAYAAJ&pg=PA142}}.</ref>

== Định nghĩa và tính chất ==
Hàm logarit nhị phân được định nghĩa là [[hàm ngược]] của hàm [[lũy thừa của 2]], vốn là một hàm số tăng trên tập hợp [[số thực]] dương và do đó có một hàm ngược duy nhất.<ref>{{citation|title=Introduction to Mathematics for Life Scientists|publisher=Springer|year=2012|first=E.|last=Batschelet|isbn=978-3-642-96080-2|url=https://books.google.com/books?id=vbT0CAAAQBAJ&pg=PA128|page=128}}.</ref> Ngoài ra, nó cũng được xác định bằng {{math|ln ''n''/ln 2}} với {{math|ln}} là [[logarit tự nhiên]]. Trong định nghĩa, khi thay logarit thực bằng [[logarit phức]] thì logarit nhị phân có thể được mở rộng cho [[số phức]].<ref>Chẳng hạn, [[Microsoft Excel]] có hàm <code>IMLOG2</code> để tính logarit nhị phân phức; xem {{citation|title=Excel Scientific and Engineering Cookbook|first=David M.|last=Bourg|publisher=O'Reilly Media|year=2006|isbn=978-0-596-55317-3|page=232|url=https://books.google.com/books?id=uKctiVg2dyIC&pg=PT248}}.</ref>

Giống như logarit thông thường, logarit nhị phân thỏa mãn các tính chất sau:<ref>{{citation|title=Algebra for College Students|first1=Bernard|last1=Kolman|first2=Arnold|last2=Shapiro|publisher=Academic Press|year=1982|isbn=978-1-4832-7121-7|url=https://books.google.com/books?id=i7vSBQAAQBAJ&pg=PA334|pages=334–335|contribution=11.4 Properties of Logarithms}}.</ref>

: <math>\log_2 xy=\log_2 x + \log_2 y</math>
: <math>\log_2\frac{x}{y}=\log_2 x - \log_2 y</math>
: <math>\log_2 x^y = y\log_2 x.</math>

Với các tính chất khác, xem [[danh sách đồng nhất thức logarit]].

== Ký hiệu ==
Trong toán học, logarit nhị phân của một số {{Math|''n''}} được ký hiệu là {{math|log<sub>2</sub>{{hsp}}''n''}}.{{Efn|Đây là ký hiệu được dùng trong [[Bách khoa toàn thư Toán học]] và [[The Princeton Companion to Mathematics]].}} Tuy nhiên, tùy theo lĩnh vực mà nó được sử dụng, còn tồn tại thêm một số ký hiệu khác.

Một số tác giả ký hiệu logarit nhị phân là {{math|lg ''n''}};<ref name="clrs">{{citation|last1=Cormen|first1=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald L.|last4=Stein|first4=Clifford|title=Introduction to Algorithms|origyear=1990|year=2001|edition=2 |publisher=MIT Press và McGraw-Hill|isbn=0-262-03293-7|pages=34, 53–54}}</ref><ref name="sw11">{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|first2=Kevin Daniel|last2=Wayne|publisher=Addison-Wesley Professional|year=2011|isbn=978-0-321-57351-3|page=185|url=https://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA185}}.</ref> đây là ký hiệu được liệt kê trong ''[[The Chicago Manual of Style]]''.<ref>{{citation|title=The Chicago Manual of Style|year=2003|edition=15 |publisher=University of Chicago Press|page=530|url=https://archive.org/details/chicagomanualofs00univ_0/page/530/mode/2up|isbn=0-226-10403-6}}.</ref> Theo [[Donald Knuth]], ký hiệu này do [[Edward Reingold]] đề xuất,<ref name="knuth">{{citation|series=[[The Art of Computer Programming]]|volume=1|title=Fundamental Algorithms|first=Donald E.|last=Knuth|authorlink=Donald Knuth|edition=3 |publisher=Addison-Wesley Professional|year=1997|isbn=978-0-321-63574-7|page=23}}.</ref> nhưng thực tế nó đã được dùng trong lý thuyết thông tin và khoa học máy tính từ trước khi Reingold bắt đầu sự nghiệp.<ref>{{citation|last=Trucco|first=Ernesto|doi=10.1007/BF02477836|journal=The Bulletin of Mathematical Biophysics|mr=0077919|pages=129–135|title=A note on the information content of graphs|volume=18|issue=2|year=1956}}.</ref><ref>{{citation|last=Mitchell|first=John N.|doi=10.1109/TEC.1962.5219391|issue=4|journal=IRE Transactions on Electronic Computers|pages=512–517|title=Computer multiplication and division using binary logarithms|volume=EC-11|year=1962}}.</ref> Logarit tự nhiên cũng được viết là {{math|log ''n''}} cùng một câu trước đó giải thích rằng cơ số mặc định của logarit là {{Math|2}}.<ref>{{citation|title=Mathematics for Engineers|first1=Georges|last1=Fiche|first2=Gerard|last2=Hebuterne|publisher=John Wiley & Sons|year=2013|isbn=978-1-118-62333-6|page=152|url=https://books.google.com/books?id=TqkckiuuXg8C&pg=PT152|quote=In the following, and unless otherwise stated, the notation {{math|log ''x''}} always stands for the logarithm to the base {{math|2}} of {{mvar|x}}}}.</ref><ref>{{citation|title=Elements of Information Theory|first1=Thomas M.|last1=Cover|first2=Joy A.|last2=Thomas|edition=2 |publisher=[[John Wiley & Sons]]|year=2012|isbn=978-1-118-58577-1|page=33|url=https://books.google.com/books?id=VWq5GG6ycxMC&pg=PT33|quote=Unless otherwise specified, we will take all logarithms to base {{math|2}}}}.</ref><ref name="gt02">{{citation|first1=Michael T.|last1=Goodrich|first2=Roberto|last2=Tamassia|title=Algorithm Design: Foundations, Analysis, and Internet Examples|publisher=John Wiley & Sons|year=2002|page=23|quote=One of the interesting and sometimes even surprising aspects of the analysis of data structures and algorithms is the ubiquitous presence of logarithms&nbsp;... As is the custom in the computing literature, we omit writing the base {{mvar|b}} of the logarithm when {{math|1=''b''&nbsp;=&nbsp;2}}.|isbn=0-471-38365-1}}</ref> Một ký hiệu khác của chính hàm số đó (đặc biệt xuất hiện trong các bài viết khoa học của [[Đức]]) là {{math|ld ''n''}}, viết tắt của cụm từ ''logarithmus dualis'' hoặc ''logarithmus dyadis'' trong [[tiếng Latinh]].<ref name="Tafel_1971">{{chú thích sách|title=Einführung in die digitale Datenverarbeitung|last=Tafel|first=Hans Jörg|date=1971|publisher=Carl Hanser Verlag|year=|isbn=3-446-10569-7|location=Munich|pages=20–21|language=de|trans-title=Giới thiệu về xử lý thông tin số}}</ref><ref name="Tietze_Schenk_1999">{{chú thích sách|url=https://archive.org/details/halbleiterschalt00tiet_103|title=Halbleiter-Schaltungstechnik|author-last1=Tietze|author-first1=Ulrich|author-last2=Schenk|author-first2=Christoph|date=1999|publisher=Springer Verlag|year=|isbn=3-540-64192-0|edition=11 |location=|page=[https://archive.org/details/halbleiterschalt00tiet_103/page/n1395 1370]|pages=|language=de}}</ref><ref name="Bauer_2009">{{chú thích sách|url=https://books.google.com/books?id=y4uTaLiN-wQC&pg=PA54|title=Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum|last=Bauer|first=Friedrich L.|publisher=[[Springer Science+Business Media]]|year=2009|isbn=978-3-642-02991-2|location=|page=54|pages=}}</ref> Các tiêu chuẩn [[DIN 1302]], [[ISO 31-11]] và [[ISO 80000-2]] còn khuyến nghị dùng một ký hiệu khác nữa, {{math|lb ''n''}}. Theo các tiêu chuẩn này, không nên dùng {{math|lg ''n''}} để ký hiệu logarit nhị phân vì nó được dùng riêng cho [[Logarit thông thường|logarit thập phân]] {{math|log<sub>10</sub> ''n''}}.<ref>Với DIN 1302 xem {{citation|title=Brockhaus Enzyklopädie in zwanzig Bänden|language=de|trans-title=Bách khoa toàn thư Brockhaus trong hai mươi tập|volume=11|page=554|publisher=F.A. Brockhaus|location=Wiesbaden|isbn=978-3-7653-0000-4|year=1970}}.</ref><ref>Với ISO 31-11 xem {{citation|last1=Thompson|first1=Ambler|last2=Taylor|first2=Barry M|date=March 2008|page=33|publisher=[[NIST]]|title=Guide for the Use of the International System of Units (SI) — NIST Special Publication 811, 2008 Edition — Second Printing|url=http://physics.nist.gov/cuu/pdf/sp811.pdf}}.</ref><ref>Với ISO 80000-2 xem {{citation|chapter-url=https://people.engr.ncsu.edu/jwilson/files/mathsigns.pdf|title=International Standard ISO 80000-2|chapter=Quantities and units – Part 2: Mathematical signs and symbols to be used in the natural sciences and technology|edition=1|date=ngày 1 tháng 12 năm 2009|at=Section 12, Exponential and logarithmic functions, tr.&nbsp;18|access-date=2020-08-23|archive-date=2019-02-28|archive-url=https://web.archive.org/web/20190228003440/https://people.engr.ncsu.edu/jwilson/files/mathsigns.pdf}}.</ref>

== Ứng dụng ==
{{Xem thêm|Thời gian nhân đôi}}

=== Lý thuyết thông tin ===
Số chữ số ([[bit]]) trong [[Hệ nhị phân|biểu diễn nhị phân]] của một số nguyên dương {{Math|''n''}} là phần nguyên của {{math|1 + log<sub>2</sub>{{hsp}}''n''}} hay bằng<ref name="sw11" />
: <math> \lfloor \log_2 n\rfloor + 1. </math>
Trong lý thuyết thông tin, định nghĩa về [[lượng thông tin]] và [[entropy thông tin]] thường được biểu diễn qua logarit nhị phân, tương ứng với việc coi bit là đơn vị cơ bản của thông tin. Tuy nhiên, còn tồn tại một số dạng khác của các định nghĩa này được biểu thị qua [[logarit tự nhiên]] và đơn vị [[Nat (đơn vị)|nat]].<ref>{{citation|title=Information Theory|first=Jan C. A.|last=Van der Lubbe|publisher=Cambridge University Press|year=1997|isbn=978-0-521-46760-5|page=3|url=https://books.google.com/books?id=tBuI_6MQTcwC&pg=PA3}}.</ref>

=== Toán học tổ hợp ===
[[Tập tin:SixteenPlayerSingleEliminationTournamentBracket.svg|nhỏ|upright=1.2|Nhánh thi đấu của một giải đấu loại trực tiếp gồm 16 người theo cấu trúc của một [[Cây nhị phân|cây nhị phân hoàn thiện]]. Chiều cao của cây đó (số vòng của giải đấu) bằng logarit nhị phân của số người tham gia giải (làm tròn đến hàng đơn vị).]]
Mặc dù logarit tự nhiên có vai trò quan trọng hơn logarit nhị phân trong nhiều lĩnh vực của [[toán học thuần túy]] như [[lý thuyết số]] và [[giải tích toán học]],<ref>{{citation|title=Taming the Infinite|first=Ian|last=Stewart|publisher=Quercus|year=2015|isbn=978-1-623-65473-3|quote=in advanced mathematics and science the only logarithm of importance is the natural logarithm|page=120|url=https://books.google.com/books?id=u4HPBAAAQBAJ&pg=PT120}}.</ref> nhưng logarit nhị phân vẫn có một số ứng dụng trong [[toán học tổ hợp]]:

* Một [[cây nhị phân]] gồm {{Math|''n''}} lá có chiều cao nhỏ nhất là {{math|log<sub>2</sub>{{hsp}}''n''}}, đạt được khi {{Math|''n''}} là [[lũy thừa của 2]] và cây đó là [[Cây nhị phân|cây nhị phân hoàn thiện]].<ref>{{citation|last=Leiss|first=Ernst L.|isbn=978-1-4200-1170-8|page=28|publisher=CRC Press|title=A Programmer's Companion to Algorithm Analysis|url=https://books.google.com/books?id=E6BNGFQ6m_IC&pg=RA2-PA28|year=2006}}.</ref> Liên quan đến nó, [[số Strahler]] lớn nhất của một hệ thống sông gồm {{Math|''n''}} dòng chảy phụ lưu là {{math|log<sub>2</sub>{{hsp}}''n'' + 1}}.<ref>{{citation|last1=Devroye|first1=L.|last2=Kruszewski|first2=P.|issue=5|journal=RAIRO Informatique Théorique et Applications|mr=1435732|pages=443–456|title=On the Horton–Strahler number for random tries|url=https://eudml.org/doc/92635|volume=30|year=1996|doi=10.1051/ita/1996300504431}}.</ref>
* [[Phép hợp|Hợp]] của một [[họ tập hợp]] bất kỳ gồm {{Math|''n''}} tập hợp khác nhau có số phần tử nhỏ nhất là {{math|log<sub>2</sub>{{hsp}}''n''}}, đạt được khi họ đó là một [[tập lũy thừa]].{{Efn|Một cách tương đương, một họ tập hợp gồm {{math|''k''}} phần tử khác nhau có nhiều nhất {{math|2<sup>''k''</sup>}} tập hợp khác nhau, đạt được khi họ đó là tập lũy thừa.}}
* Một [[hình lập phương riêng]] {{Math|''n''}} đỉnh có số chiều đẳng cự nhỏ nhất là {{math|log<sub>2</sub>{{hsp}}''n''}} và số cạnh lớn nhất là {{math|{{sfrac|1|2}}''n'' log<sub>2</sub>{{hsp}}''n''}}, đạt được khi hình đó là [[đồ thị hình siêu lập phương]].<ref>{{citation|last=Eppstein|first=David|authorlink=David Eppstein|arxiv=cs.DS/0402028|doi=10.1016/j.ejc.2004.05.001|issue=5|journal=European Journal of Combinatorics|mr=2127682|pages=585–592|title=The lattice dimension of a graph|volume=26|year=2005}}.</ref>
* Theo [[định lý Ramsey]], một [[đồ thị vô hướng]] {{Math|''n''}} đỉnh có một [[clique]] hoặc một [[tổ hợp độc lập]] với cấp [[tỉ lệ thuận]] với logarit của {{Math|''n''}}. Chưa rõ cấp chính xác của nó là bao nhiêu nhưng các khoảng giá trị gần đúng nhất của cấp đó có liên quan đến logarit nhị phân. Đặc biệt, mọi đồ thị đều có một clique hoặc tổ hợp độc lập với cấp nhỏ nhất là {{math|{{sfrac|1|2}}log<sub>2</sub>{{hsp}}''n'' (1 − ''o''(1))}} và hầu hết mọi đồ thị không có một clique hoặc tổ hợp độc lập với cấp lớn hơn {{math|2log<sub>2</sub>{{hsp}}''n'' (1 + ''o''(1))}}.<ref>{{citation|last1=Graham|first1=Ronald L.|last2=Rothschild|first2=Bruce L.|last3=Spencer|first3=Joel H.|page=78|publisher=Wiley-Interscience|title=Ramsey Theory|year=1980|isbn=0-471-05997-8|url=https://books.google.com/books?id=S-juAAAAMAAJ}}.</ref>
* Dựa trên một phân tích toán học của [[mô hình Gilbert–Shannon–Reeds]] về xáo bài ngẫu nhiên, có thể thấy số lần [[Xáo bài|chẽ bài]] mà một người cần thực hiện để sau đó một bộ bài {{Math|''n''}} lá được phân phối [[hoán vị]] ngẫu nhiên gần đều là xấp xỉ {{math|{{sfrac|3|2}}log<sub>2</sub>{{hsp}}''n''}} lần. Tính toán này là cơ sở để phát biểu rằng tốt nhất một bộ bài 52 lá phải được xáo 7 lần.<ref>{{citation|last1=Bayer|first1=Dave|last2=Diaconis|first2=Persi|issue=2|journal=The Annals of Applied Probability|jstor=2959752|mr=1161056|pages=294–313|title=Trailing the dovetail shuffle to its lair|volume=2|year=1992|doi=10.1214/aoap/1177005705}}.</ref>

=== Độ phức tạp tính toán ===
[[Tập tin:Binary search into array - example.svg|nhỏ|upright=1.2|[[Tìm kiếm nhị phân]] trên một mảng đã sắp xếp, một thuật toán có độ phức tạp tính toán liên quan đến logarit nhị phân]]
Do số học nhị phân được dùng nhiều trong [[thuật toán]] nên logarit nhị phân xuất hiện thường xuyên trong [[phân tích thuật toán]] theo phân nhánh nhị phân.<ref name="knuth" /><ref name="gt02" /> Nếu một bài toán có {{Math|''n''}} cách giải và mỗi vòng lặp của thuật toán làm giảm số cách giải đi một nửa thì số vòng lặp cần để cho ra một câu trả lời duy nhất là phần nguyên của {{math|log<sub>2</sub>{{hsp}}''n''}}. Ý tưởng này được ứng dụng khi phân tích một số thuật toán và [[cấu trúc dữ liệu]]. Ví dụ, trong [[tìm kiếm nhị phân]], kích thước của bài toán cần giải giảm đi một nửa sau mỗi vòng lặp, và do đó cần {{math|log<sub>2</sub>{{hsp}}''n''}} vòng lặp để cho câu trả lời đối với một bài toán kích thước {{Math|''n''}}.<ref>{{citation|title=Algorithms and Data Structures: The Basic Toolbox|first1=Kurt|last1=Mehlhorn|first2=Peter|last2=Sanders|publisher=Springer|year=2008|isbn=978-3-540-77977-3|pages=34–36|contribution=2.5 An example – binary search|url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Introduction.pdf}}.</ref> Tương tự, một [[cây tìm kiếm nhị phân]] cân bằng chứa {{Math|''n''}} phần tử có chiều cao là {{math|log<sub>2</sub>(''n'' + 1) − 1}}.<ref>{{citation|title=Applied Combinatorics|first1=Fred|last1=Roberts|first2=Barry|last2=Tesman|edition=2 |publisher=CRC Press|year=2009|isbn=978-1-4200-9983-6|page=206|url=https://books.google.com/books?id=szBLJUhmYOQC&pg=PA206}}.</ref>

Thời gian hoạt động của một thuật toán thường được biểu diễn qua [[Kí hiệu O lớn|ký hiệu O lớn]], dùng để rút gọn biểu thức bằng cách bỏ qua hằng số tỉ lệ và hạng tử bậc thấp. Vì logarit cơ số khác nhau chỉ sai khác nhau bởi một hằng số tỉ lệ nên thuật toán hoạt động trong thời gian {{math|''O''(log<sub>2</sub>{{hsp}}''n'')}} cũng có thể nói là hoạt động trong thời gian {{math|''O''(log<sub>13</sub>''n'')}}. Do đó, cơ số của logarit trong các biểu thức như {{math|''O''(log ''n'')}} hay {{math|''O''(''n'' log ''n'')}} không quan trọng và có thể bỏ qua.<ref name="clrs" /><ref>{{citation|title=Introduction to the Theory of Computation|first=Michael|last=Sipser|edition=3 |publisher=Cengage Learning|year=2012|isbn=978-1-133-18779-0|contribution=Example 7.4|url=https://books.google.com/books?id=P3f6CAAAQBAJ&pg=PA277|pages=277–278}}.</ref> Tuy nhiên, nếu logarit xuất hiện trên số mũ của một khoảng thời gian thì không thể bỏ qua cơ số của logarit đó. Chẳng hạn, {{math|''O''(2<sup>log<sub>2</sub>{{hsp}}''n''</sup>)}} không giống với {{math|''O''(2<sup>ln ''n''</sup>)}} vì khoảng thời gian thứ nhất bằng với {{math|''O''(''n'')}} trong khi khoảng thời gian thứ hai bằng với {{math|''O''(''n''<sup>0,6931...</sup>)}}.

Một số ví dụ về thuật toán có thời gian hoạt động là {{math|''O''(log ''n'')}} hoặc {{math|''O''(''n'' log ''n'')}} là:

* [[Sắp xếp nhanh]] (thời gian trung bình) và các thuật toán [[sắp xếp so sánh]] khác<ref>{{Harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=156}}; {{Harvnb|Goodrich|Tamassia|2002|p=238}}.</ref>
* Tìm kiếm trong [[cây tìm kiếm nhị phân]] cân bằng<ref>{{Harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=276}}; {{Harvnb|Goodrich|Tamassia|2002|p=159}}.</ref>
* [[Thuật toán bình phương và nhân|Bình phương và nhân]]<ref>{{Harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=879–880}}; {{Harvnb|Goodrich|Tamassia|2002|p=464}}.</ref>
* [[Dãy con tăng dài nhất]]<ref>{{citation|title=How to Think About Algorithms|first=Jeff|last=Edmonds|publisher=Cambridge University Press|year=2008|isbn=978-1-139-47175-6|page=302|url=https://books.google.com/books?id=hGuixQMQS_0C&pg=PT280}}.</ref>

Logarit nhị phân cũng xuất hiện trong số mũ của khoảng thời gian để một số [[thuật toán chia để trị]] hoạt động, chẳng hạn như [[thuật toán Karatsuba]] dùng để nhân các số {{Math|''n''}} bit trong thời gian {{math|''O''(''n''<sup>log<sub>2</sub>{{hsp}}3</sup>)}},<ref>{{Harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=844}}; {{Harvnb|Goodrich|Tamassia|2002|p=279}}.</ref> và [[thuật toán Strassen]] dùng để nhân ma trận {{math|''n'' &times; ''n''}} trong khoảng thời gian {{math|''O''(''n''<sup>log<sub>2</sub>{{hsp}}7</sup>)}}.<ref>{{Harvnb|Cormen|Leiserson|Rivest|Stein|2001|loc=mục 28.2}}.</ref> Sự xuất hiện của logarit nhị phân trong các khoảng thời gian đó có thể được giải thích bằng cách liên hệ với [[Định lý thợ (phân tích thuật toán)|định lý thợ cho hệ thức truy hồi chia để trị]].

=== Tin sinh học ===
[[Tập tin:Mouse cdna microarray.jpg|nhỏ|upright=1|Một microarray gồm khoảng 8700 gen. Tốc độ biểu hiện của các gen này được so sánh qua logarit nhị phân.]]
Trong [[tin sinh học]], [[microarray]] được dùng để đo mức độ [[biểu hiện gen]] trong một mẫu nguyên liệu sinh học. Các tốc độ biểu hiện khác nhau của một gen thường được so sánh bằng cách lấy logarit nhị phân của tỉ số giữa chúng: tỉ số log của hai tốc độ biểu hiện gen được định nghĩa là logarit nhị phân của tỉ số giữa chúng. Logarit nhị phân giúp việc so sánh tốc độ biểu hiện gen trở nên thuận lợi: chẳng hạn, tốc độ biểu hiện gen nhân đôi tương ứng với tỉ số log là {{math|1}}, tốc độ giảm một nửa tương ứng với tỉ số log là {{math|−1}} và tốc độ không đổi tương ứng với tỉ số log bằng không.<ref>{{citation|title=Microarray Gene Expression Data Analysis: A Beginner's Guide|first1=Helen|last1=Causton|first2=John|last2=Quackenbush|first3=Alvis|last3=Brazma|publisher=John Wiley & Sons|year=2009|isbn=978-1-4443-1156-3|pages=49–50|url=https://books.google.com/books?id=bg6D_7mdG70C&pg=PA49}}.</ref>

Các điểm dữ liệu thu được bằng cách này thường được minh họa thành một [[biểu đồ phân tán]] có một hoặc cả hai trục đều là logarit nhị phân của tỉ lệ tốc độ, hoặc thông qua các loại biểu đồ như [[Biểu đồ MA|MA]] và [[Biểu đồ RA|RA]] để quay và phóng to hoặc thu nhỏ biểu đồ phân tán đó.<ref>{{citation|title=Computational and Statistical Methods for Protein Quantification by Mass Spectrometry|first1=Ingvar|last1=Eidhammer|first2=Harald|last2=Barsnes|first3=Geir Egil|last3=Eide|first4=Lennart|last4=Martens|publisher=John Wiley & Sons|year=2012|isbn=978-1-118-49378-6|page=105|url=https://books.google.com/books?id=3Z3VbhLz6pMC&pg=PA105}}.</ref>

=== Lý thuyết âm nhạc ===
Trong [[lý thuyết âm nhạc]], [[Quãng (âm nhạc)|quãng]] giữa hai [[tông nhạc]] được xác định bằng tỉ lệ tần số của chúng. Các quãng âm có từ tỉ số [[số hữu tỉ]] với tử số và mẫu số nhỏ đều được xem là đặc biệt êm tai, nhịp nhàng. Trong đó, quãng âm đơn giản nhất và quan trọng nhất là [[quãng tám]] với tỉ lệ tần số là {{math|2:1}}. Số quãng tám nằm giữa hai tông nhạc là logarit nhị phân của tỉ lệ tần số của chúng.<ref name="mga">{{citation|title=The Musician's Guide to Acoustics|first1=Murray|last1=Campbell|first2=Clive|last2=Greated|publisher=Oxford University Press|year=1994|isbn=978-0-19-159167-9|page=78|url=https://books.google.com/books?id=iiCZwwFG0x0C&pg=PA78}}.</ref>

Để nghiên cứu [[Chuỗi nốt nhạc|hệ thống điều chỉnh cao độ]] và các khía cạnh khác của lý thuyết âm nhạc vốn cần sự phân biệt tinh vi hơn giữa các tông nhạc, cần có một [[độ đo]] để đo một quãng nhỏ hơn nhiều so với quãng tám và có tính cộng (giống logarit) thay vì tính nhân (giống tỉ lệ tần số). Theo đó, nếu ba tông {{mvar|x}}, {{mvar|y}}, {{mvar|z}} tạo thành một chuỗi tông nhạc với cao độ tăng dần thì độ đo của quãng từ {{mvar|x}} đến {{mvar|y}} cộng với độ đo của quãng từ {{mvar|y}} đến {{mvar|z}} phải bằng độ đo của quãng từ {{mvar|x}} đến {{mvar|z}}. Một độ đo như thế được cho bằng đơn vị [[Cent (âm nhạc)|cent]], một đơn vị chia quãng tám thành 1200 quãng bằng nhau (12 [[nửa cung]], mỗi cung gồm 100 cent). Cho hai tông nhạc với chu kỳ {{math|''f''<sub>1</sub>}} và {{math|''f''<sub>2</sub>}}, khi đó số cent trong quãng từ {{math|''f''<sub>1</sub>}} đến {{math|''f''<sub>2</sub>}} là<ref name="mga" />
: <math>\left|1200\log_2\frac{f_1}{f_2}\right|.</math>

=== Tổ chức giải đấu thể thao ===
Trong các giải đấu thể thao gồm hai người (hoặc đội) thi đấu mỗi trận, logarit nhị phân cho biết số vòng đấu mà một [[giải đấu loại trực tiếp]] cần có để xác định nhà vô địch. Ví dụ, một giải gồm 4 người cần {{math|1=log<sub>2</sub>{{hsp}}4 = 2}} vòng để tìm nhà vô địch, một giải gồm 32 đội cần {{math|1=log<sub>2</sub>{{hsp}}32 = 5}} vòng, ... Trong trường hợp giải có {{Math|''n''}} người/đội tham gia mà {{Math|''n''}} không phải là lũy thừa của 2 thì {{math|log<sub>2</sub>{{hsp}}''n''}} được làm tròn lên vì cần có ít nhất một vòng đấu nữa mà trong đó có một số người/đội không tham gia. Chẳng hạn, {{math|log<sub>2</sub>{{hsp}}6}} gần bằng {{math|2,585}}, làm tròn lên thành {{math|3}}, nghĩa là một giải đấu gồm 6 đội cần có 3 vòng đấu (cho hai đội ngồi ngoài vòng thứ nhất hoặc một đội ngồi ngoài vòng thứ hai). Số vòng như vậy cũng là cần thiết để xác định nhà vô địch trong một [[giải đấu hệ Thụy Sĩ]].<ref>{{citation|title=Introduction to Physical Education and Sport Science|first=Robert|last=France|publisher=Cengage Learning|year=2008|isbn=978-1-4180-5529-5|page=282|url=https://books.google.com/books?id=dH2nB1CX2SMC&pg=PA282}}.</ref>

=== Nhiếp ảnh ===
Trong [[nhiếp ảnh]], [[giá trị phơi sáng]] được đo bằng logarit nhị phân của lượng ánh sáng tới màn ảnh hoặc [[cảm biến]] ảnh, phù hợp với [[luật Weber–Fechner]] mô tả phản ứng logarit của hệ thống thị giác con người với ánh sáng. Một bước ("khẩu") phơi sáng tương ứng với một đơn vị trong thang đo logarit cơ số 2.<ref>{{citation|title=The Manual of Photography|first1=Elizabeth|last1=Allen|first2=Sophie|last2=Triantaphillidou|publisher=Taylor & Francis|year=2011|isbn=978-0-240-52037-7|page=228|url=https://books.google.com/books?id=IfWivY3mIgAC&pg=PA228}}.</ref><ref name="btzs">{{citation|title=Beyond the Zone System|first=Phil|last=Davis|publisher=CRC Press|year=1998|isbn=978-1-136-09294-7|page=17|url=https://books.google.com/books?id=YaVEAQAAQBAJ&pg=PA17}}.</ref> Chính xác hơn, giá trị phơi sáng của một bức ảnh bằng

: <math>\log_2 \frac{N^2}{t}</math>

trong đó {{mvar|N}} là [[chỉ số khẩu độ]] (số f) đo [[độ mở]] của ống kính khi phơi sáng và {{mvar|t}} là số giây phơi sáng.<ref>{{Harvnb|Allen|Triantaphillidou|2011|p=235}}.</ref>

Logarit nhị phân cũng được dùng khi biểu diễn [[dải tương phản động]] của vật liệu nhạy sáng hoặc cảm biến kỹ thuật số.<ref>{{citation|title=Visual Effects Society Handbook: Workflow and Techniques|first1=Susan|last1=Zwerman|first2=Jeffrey A.|last2=Okun|publisher=CRC Press|year=2012|isbn=978-1-136-13614-6|page=205|url=https://books.google.com/books?id=3rLpAwAAQBAJ&pg=PA205}}.</ref>

== Tính toán ==
[[Tập tin:SR-50 early TI calculator.agr.jpg|nhỏ|upright=0.75|Máy tính bỏ túi TI SR-50 (1974). Phím ln và log nằm ở hàng phím thứ hai; máy không có phím log<sub>2</sub>.]]

=== Đổi cơ số ===
Một cách dễ dàng để tính {{math|log<sub>2</sub>{{hsp}}''n''}} trên các [[máy tính]] không có sẵn hàm {{math|log<sub>2</sub>}} là thông qua hàm [[logarit tự nhiên]] ({{math|ln}}) hoặc [[Logarit thông thường|logarit thập phân]] ({{math|log}} hoặc {{math|log<sub>10</sub>}}), có thể được tìm thấy trong hầu hết máy tính bỏ túi. Theo [[Logarit#Đổi cơ số|công thức đổi cơ số]] thì:<ref name="btzs" /><ref>{{citation|title=Secret History: The Story of Cryptology|first=Craig P.|last=Bauer|publisher=CRC Press|year=2013|isbn=978-1-4665-6186-1|page=332|url=https://books.google.com/books?id=EBkEGAOlCDsC&pg=PA332}}.</ref>

: <math>\log_2 n = \frac{\ln n}{\ln 2} = \frac{\log_{10} n}{\log_{10} 2},</math>

hay

: <math>\log_2 n \approx 1,442695\ln n \approx 3,321928\log_{10} n.</math>

=== Làm tròn số nguyên ===
Logarit nhị phân có thể được làm thành một hàm với đầu vào là số nguyên và trả về số nguyên bằng cách [[làm tròn]] nó lên hay xuống. Hai dạng này của logarit nhị phân nguyên được liên hệ bằng công thức:<ref name="Warren_2002">{{citation|title=Hacker's Delight|first=Henry S.|last=Warren Jr.|date=2002|edition=1 |publisher=Addison Wesley|isbn=978-0-201-91465-8|page=215}}.</ref>

: <math> \lfloor \log_2(n) \rfloor = \lceil \log_2(n + 1) \rceil - 1 \text{ nếu }n \ge 1.</math>

Có thể mở rộng định nghĩa này bằng cách quy ước <math> \lfloor \log_2(0) \rfloor = -1</math>. Khi đó, hàm này có liên hệ với [[số bit 0 đứng trước]] trong biểu diễn nhị phân không dấu 32 bit của {{mvar|n}}, {{math|nlz(''n'')}}:<ref name="Warren_2002" />

: <math>\lfloor \log_2(n) \rfloor = 31 - \operatorname{nlz}(n).</math>

Logarit nhị phân nguyên có thể được xác định là chỉ số của bit 1 có trọng số cao nhất trong đầu vào (tính từ số 0). Trong trường hợp này, đó chính là phần bù của phép toán [[tìm bit 1 đầu tiên]], dùng để tìm chỉ số của bit 1 có trọng số thấp nhất. Nhiều nền tảng phần cứng có hỗ trợ tìm số bit 0 đứng trước hoặc các phép toán tương đương, cho phép tìm logarit nhị phân một cách nhanh chóng. Các hàm <code>fls</code> và <code>flsl</code> trong [[hạt nhân Linux]]<ref>{{Chú thích web|url=https://www.kernel.org/doc/htmldocs/kernel-api/API-fls.html|tựa đề=fls|tác giả=|họ=|tên=|ngày=|website=Linux kernel API|nhà xuất bản=kernel.org|url lưu trữ=|ngày lưu trữ=|url hỏng=|ngày truy cập=2020-08-22}}</ref> và trong một số phiên bản của thư viện phần mềm [[Thư viện chuẩn C|libc]] cũng tính được logarit nhị phân (làm tròn thành số nguyên cộng 1).

=== Tính gần đúng bằng phép lặp ===
Với một [[Số dương|số thực dương]] bất kỳ, logarit nhị phân có thể được chia thành hai phần để tính.<ref name="ml73">{{citation|last1=Majithia|first1=J. C.|last2=Levan|first2=D.|doi=10.1109/PROC.1973.9318|issue=10|journal=Proceedings of the IEEE|pages=1519–1520|title=A note on base-2 logarithm computations|volume=61|year=1973}}.</ref> Trước tiên, ta tính [[phần nguyên]] <math>\lfloor\log_2 x\rfloor</math> để đưa về thành bài toán mà trong đó đối số của logarit nằm trong nửa khoảng [1, 2), từ đó rút gọn bước thứ hai là tính phần thập phân của logarit. Với {{math|''x'' > 0}}, tồn tại duy nhất một số nguyên {{mvar|n}} sao cho {{math|2<sup>''n''</sup> ≤ ''x'' < 2<sup>''n''+1</sup>}} hay {{math|1 ≤ 2<sup>−''n''</sup>''x'' < 2}}. Từ lập luận này, ta suy ra được phần nguyên của logarit là {{mvar|n}} và phần thập phân là {{math|log<sub>2</sub>(2<sup>−''n''</sup>''x'')}}.<ref name="ml73" /> Nói cách khác:

: <math>\log_2 x = n + \log_2 y \quad\text{với } y = 2^{-n}x \text{ và } y \in [1,2).</math>

Với [[số thực dấu phẩy động]], phần nguyên là số mũ dấu phẩy động,<ref>{{citation|title=Production Rendering: Design and Implementation|first=Ian|last=Stephenson|publisher=Springer-Verlag|year=2005|isbn=978-1-84628-085-6|url=https://books.google.com/books?id=BCC5aTR34C4C&pg=PA270|pages=270–273|contribution=9.6 Fast Power, Log2, and Exp2 Functions}}.</ref> còn đối với số nguyên thì nó được xác định bằng cách thực hiện phép toán đếm [[số bit 0 đứng trước]].<ref name="Warren_2013">{{Citation|title=Hacker's Delight|first=Henry S.|last=Warren Jr.|date=2013|orig-year=2002|edition=2 |publisher=Addison Wesley – Pearson Education, Inc.|isbn=978-0-321-84268-8|id=0-321-84268-5|page=291|contribution=11-4: Integer Logarithm|contribution-url=https://books.google.com/books?id=XD9iAwAAQBAJ&pg=PA291}}.</ref>

Phần thập phân của kết quả thu được là {{math|log<sub>2</sub>{{hsp}}''y''}} và có thể được tính chỉ bằng [[phép lặp]] cùng các [[phép nhân]] và [[phép chia]] cơ bản.<ref name="ml73" /> Thuật toán tính phần thập phân có thể được mô tả bằng [[mã giả]] như sau:

# Bắt đầu với một số thực {{mvar|y}} thuộc nửa khoảng {{math|[1,&nbsp;2)}}. Nếu {{math|1=''y'' = 1}} thì thuật toán kết thúc và phần thập phân bằng 0.
# Ngược lại, bình phương {{mvar|y}} lặp lại đến khi kết quả {{mvar|z}} thuộc nửa khoảng {{math|[2,&nbsp;4)}}. Gọi {{mvar|m}} là số lần bình phương cần thực hiện. Khi đó {{math|1=''z'' = ''y''<sup>2<sup>''m''</sup></sup>}} với {{mvar|m}} là giá trị sao cho {{mvar|z}} thuộc {{math|[2,&nbsp;4)}}.
# Lấy logarit nhị phân cho cả hai vế rồi biến đổi đại số:
#:<math>\begin{align}
 \log_2 z &= 2^m \log_2 y \\
 \log_2 y &= \frac{ \log_2 z }{ 2^m } \\
          &= \frac{ 1 + \log_2(z/2) }{ 2^m } \\
          &= 2^{-m} + 2^{-m}\log_2(z/2).
\end{align}</math>
# Một lần nữa {{math|''z''/2}} là số thực trong nửa khoảng {{math|[1,&nbsp;2)}}. Trở lại bước 1 và tính logarit nhị phân của {{math|''z''/2}} theo cách trên.
#
Kết quả cuối cùng được biểu diễn bằng các công thức đệ quy sau với {{math|''m''<sub>''i''</sub>}} là số lần bình phương trong vòng lặp thứ {{mvar|i}} của thuật toán:

: <math>\begin{align}
 \log_2 x &= n + 2^{-m_1} \left(1 + 2^{-m_2} \left(1 + 2^{-m_3} \left(1 + \cdots \right)\right)\right) \\
          &= n + 2^{-m_1} + 2^{-m_1-m_2} + 2^{-m_1-m_2-m_3} + \cdots
\end{align} </math>

Trong trường hợp đặc biệt khi phần thập phân ở bước 1 được xác định là bằng 0, đó là một chuỗi hữu hạn kết thúc tại một số hạng nào đó. Ngược lại, đó là một [[chuỗi vô hạn]] [[Chuỗi hội tụ|hội tụ]] theo [[dấu hiệu d'Alembert]] vì mỗi số hạng luôn nhỏ hơn số hạng liền trước (do {{math|''m''<sub>''i''</sub> > 0}}). Khi ứng dụng thực tế, phải cắt ngắn đi chuỗi vô hạn này để đạt kết quả gần đúng. Nếu chuỗi dừng lại ở số hạng thứ {{mvar|i}} thì sai số trong kết quả là nhỏ hơn {{math|2<sup>−(''m''<sub>1</sub> + ''m''<sub>2</sub>{{hsp}}+ ... + ''m''<sub>''i''</sub>)</sup>}}.<ref name="ml73" />

=== Trong thư viện phần mềm ===
Hàm <code>log2</code> là một hàm toán học nằm trong [[Thư viện chuẩn C|thư viện chuẩn]] của [[C (ngôn ngữ lập trình)|ngôn ngữ C]]. Dạng mặc định của hàm này yêu cầu đối số với [[độ chính xác kép]] (kiểu <code>double</code>) nhưng một số dạng khác của hàm cho phép đối số có độ chính xác đơn (kiểu <code>float</code>) hoặc độ chính xác kép mở rộng (kiểu <code>long double</code>).<ref>{{citation|url=http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf|title=ISO/IEC 9899:1999 specification|page=226|contribution=7.12.6.10 The log2 functions|archiveurl=http://web.archive.org/web/20051015193126/http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf|archive-date = ngày 15 tháng 10 năm 2005 |access-date = ngày 31 tháng 8 năm 2020}}.</ref> Trong [[MATLAB]], đối số của hàm <code>log2</code> có thể là [[số âm]], và trong trường hợp này thì đầu ra của hàm là một [[số phức]].<ref>{{citation|title=The Matlab® 5 Handbook|first1=Darren|last1=Redfern|first2=Colin|last2=Campbell|publisher=Springer-Verlag|year=1998|isbn=978-1-4612-2170-8|url=https://books.google.com/books?id=KQDaBwAAQBAJ&pg=PA141|page=141}}.</ref>

== Ghi chú ==
{{notelist|30em}}
== Tham khảo ==
{{Tham khảo|30em}}

== Liên kết ngoài ==
*{{mathworld|id=BinaryLogarithm|title=Binary Logarithm}}
*{{citation|url=http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog|title=Find the log base 2 of an N-bit integer in O(lg(N)) operations|work=Bit Twiddling Hacks|first=Sean Eron|last=Anderson|publisher=Stanford University|date = ngày 12 tháng 12 năm 2003 |access-date = ngày 23 tháng 8 năm 2020}}
*[http://longnow.org/essays/richard-feynman-and-connection-machine/ Feynman and the Connection Machine]

{{Sao bài viết tốt|phiên bản được chọn=63824425|thời gian=22 tháng 9 năm 2020}}

[[Thể loại:Vi tích phân]]
[[Thể loại:Lôgarit]]