{"id":352956,"date":"2024-05-20T22:18:30","date_gmt":"2024-05-20T22:18:30","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=352956"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-05-20T22:18:30","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=352956","title":{"rendered":"<span>\u0411\u044b\u0441\u0442\u0440\u044b\u0439 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\"><a href=\"https:\/\/habr.com\/ru\/companies\/ruvds\/articles\/756422\/\"><\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/s0\/mp\/j5\/s0mpj5nfcn1lrqfw1k3yt56f4b8.png\" data-src=\"https:\/\/habrastorage.org\/webt\/s0\/mp\/j5\/s0mpj5nfcn1lrqfw1k3yt56f4b8.png\"\/><\/div>\n<p><\/a><br \/>  \u041c\u043e\u0438 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0438 \u2014 \u0437\u0430\u043d\u044f\u0442\u044b\u0435 \u043b\u044e\u0434\u0438, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0440\u0430\u0437\u0443 \u043f\u0435\u0440\u0435\u0439\u0434\u0443 \u043a \u0434\u0435\u043b\u0443. \u0412\u043e\u0442 \u043e\u043d\u0430, \u0441\u0430\u043c\u0430\u044f \u0431\u044b\u0441\u0442\u0440\u0430\u044f \u043e\u0431\u043e\u0431\u0449\u0451\u043d\u043d\u0430\u044f (\u0438 \u043f\u0440\u043e\u0441\u0442\u0430\u044f) \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0430 C++:<\/p>\n<pre><code class=\"cpp\">template &lt;class ForwardIt, class T, class Compare> constexpr ForwardIt sb_lower_bound(       ForwardIt first, ForwardIt last, const T&amp; value, Compare comp) {    auto length = last - first;    while (length > 0) {       auto rem = length % 2;       length \/= 2;       if (comp(first[length], value)) {          first += length + rem;       }    }    return first; }<\/code><\/pre>\n<p>  \u0422\u043e\u0442 \u0436\u0435 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u0447\u0442\u043e \u0438 \u0443 <code>std::lower_bound<\/code>, \u043d\u043e <strong><font color=\"#3AC1EF\">\u0432\u0434\u0432\u043e\u0435<\/font><\/strong> \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438 \u043a\u043e\u0440\u043e\u0447\u0435. \u00ab\u0411\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f\u00bb, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e <code>if<\/code> \u043a\u043e\u043c\u043f\u0438\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043c\u0430\u043d\u0434\u0443 \u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0438, \u0430 \u043d\u0435 \u0432 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0435\/\u0443\u0441\u043b\u043e\u0432\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0445\u043e\u0434. \u0411\u043b\u0438\u0436\u0435 \u043a \u043a\u043e\u043d\u0446\u0443 \u0441\u0442\u0430\u0442\u044c\u0438 \u043c\u044b \u0438\u0437\u0443\u0447\u0438\u043c \u043e\u043f\u0446\u0438\u0438 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430 \u0438 \u0434\u0430\u0436\u0435 \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u044b\u0435 \u0432\u0435\u0440\u0441\u0438\u0438 \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f. \u0414\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 \u043d\u0435 \u043d\u0443\u0436\u043d\u044b \u043e\u0441\u043e\u0431\u044b\u0435 \u0437\u043d\u0430\u043d\u0438\u044f \u0432 C++. \u0414\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c, \u0447\u0442\u043e \u0438\u0442\u0435\u0440\u0430\u0442\u043e\u0440\u044b (<code>first<\/code> \u0438 <code>last<\/code>) \u043f\u043e \u0441\u0443\u0442\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f\u043c\u0438 \u043d\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0445\u043e\u0442\u044f \u043c\u043e\u0433\u0443\u0442 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u043d\u0430 \u043e\u0434\u0438\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u0430\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u041c\u043e\u0436\u0435\u0442\u0435 \u043d\u0435 \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043d\u0430 <code>template<\/code>, <code>class<\/code>, <code>constexpr<\/code> \u0438 <code>&amp;<\/code>. \u0412\u043e\u0442 \u0435\u0441\u043b\u0438 \u0431\u044b \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043b \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438 \u0447\u0438\u0441\u0442\u044b\u0439 \u044f\u0437\u044b\u043a, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 \u0436\u0435\u043b\u0435\u0437\u0430&#8230;<sup><a href=\"#1\">1<\/a><\/sup> <sup><a href=\"#2\">2<\/a><\/sup><a name=\"habracut\"><\/a><\/p>\n<h2><font color=\"#3AC1EF\">\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a<\/font><\/h2>\n<p>  \u0423 \u043d\u0430\u0441 \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a, \u0438 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438, \u043a\u0443\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c <code>value<\/code>. \u0412 C++ \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f <code>std::lower_bound<\/code>, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0449\u0430\u044f \u043f\u0435\u0440\u0432\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e (\u0438\u0442\u0435\u0440\u0430\u0442\u043e\u0440), \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 (\u043e\u0431\u044b\u0447\u043d\u043e <code>&lt;<\/code>) \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 false, \u0438\u043b\u0438 <code>last<\/code>, \u0435\u0441\u043b\u0438 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0438\u0441\u0442\u0438\u043d\u043d\u043e \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/p>\n<p>  <code>\u0414\u0432\u043e\u0438\u0447\u043d\u044b\u043c<\/code> \u043f\u043e\u0438\u0441\u043a \u043d\u0430\u0437\u0432\u0430\u043d \u043f\u043e\u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0435\u0442 \u0441\u043f\u0438\u0441\u043e\u043a \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438 \u043f\u043e \u043a\u0430\u043a\u043e\u043c\u0443-\u0442\u043e \u0441\u0440\u0435\u0434\u043d\u0435\u043c\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0443, \u0430 \u0437\u0430\u0442\u0435\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0441 \u043d\u0443\u0436\u043d\u044b\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c <code>value<\/code>. \u0418\u0441\u0445\u043e\u0434\u044f \u0438\u0437 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u043c\u044b \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u043e\u0434\u0438\u043d \u0438\u0437 \u0434\u0432\u0443\u0445 \u0441\u043f\u0438\u0441\u043a\u043e\u0432, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0442\u044c \u043f\u043e\u0438\u0441\u043a. \u041c\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u0441\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u0441 \u043d\u0435\u043a\u043e\u0439 \u0434\u043b\u0438\u043d\u043e\u0439 <code>length = last - first<\/code>, \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0435\u0433\u043e\u0441\u044f \u0441 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0438\u0442\u0435\u0440\u0430\u0442\u043e\u0440\u0430 <code>first<\/code>. \u041d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0446\u0438\u043a\u043b, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435, \u043f\u043e\u043a\u0430 \u0441\u043f\u0438\u0441\u043e\u043a \u043d\u0435 \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043f\u0443\u0441\u0442\u044b\u043c, \u0442\u043e \u0435\u0441\u0442\u044c <code>while (length > 0)<\/code>. \u0412\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0443 \u0432 <code>length \/ 2<\/code>, \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0438 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a, \u0447\u0442\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f <code>first<\/code> \u0438 <code>length<\/code>. \u0412\u043e\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"cpp\">\/\/ std_lower_bound() auto length = last - first; while (length > 0) {    auto half = length \/ 2;    if (comp(first[half], value)) {       first += half + 1;       length -= half + 1;    } else {       length = half;    } } return first;<\/code><\/pre>\n<p>  \u0412\u0441\u0451 \u043f\u0440\u043e\u0441\u0442\u043e. \u041c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0441\u043b\u0435\u0433\u043a\u0430 \u043e\u0442\u0440\u0435\u0444\u0430\u043a\u0442\u043e\u0440\u0435\u043d\u043d\u0443\u044e \u0432\u0435\u0440\u0441\u0438\u044e, <a href=\"https:\/\/github.com\/gcc-mirror\/gcc\/blob\/releases\/gcc-13\/libstdc%2B%2B-v3\/include\/bits\/stl_algobase.h#L1467\">\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 gcc\/libstdc++<\/a>, \u0438\u043b\u0438 \u0432 <a href=\"https:\/\/github.com\/llvm\/llvm-project\/blob\/release\/16.x\/libcxx\/include\/__algorithm\/lower_bound.h#L36\">llvm\/libc++<\/a>. \u041e\u043d\u0438 \u0438\u043c\u0435\u044e\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u0443\u044e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0438 \u0434\u0430\u0436\u0435 \u043a\u043e\u043c\u043f\u0438\u043b\u0438\u0440\u0443\u044e\u0442\u0441\u044f (\u0438\u043d\u043e\u0433\u0434\u0430) \u0432 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0439 \u043a\u043e\u0434 \u0432 \u0446\u0438\u043a\u043b\u0435.<\/p>\n<h2><font color=\"#3AC1EF\">\u041f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f<\/font><\/h2>\n<p>  \u00ab\u0427\u0442\u043e \u0436\u0435 \u0432 \u044d\u0442\u043e\u043c \u043a\u043e\u0434\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0433\u043e?\u00bb \u041f\u043e\u0447\u0442\u0438 \u043d\u0438\u0447\u0435\u0433\u043e, \u043d\u043e \u044f \u0440\u0430\u0434, \u0447\u0442\u043e \u0432\u044b \u0441\u043f\u0440\u043e\u0441\u0438\u043b\u0438. \u041e\u0442\u043b\u0438\u0447\u043d\u044b\u0439 \u0432\u043e\u043f\u0440\u043e\u0441. \u0417\u0430 \u0434\u043e\u043b\u0433\u0438\u0435 \u0433\u043e\u0434\u044b \u0440\u0430\u0437\u0432\u0438\u0442\u0438\u044f \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u044b \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043b\u0438\u0441\u044c \u0432\u0441\u0451 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0438 \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f <em>\u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044e \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f<\/em>. \u041a\u0440\u0430\u0442\u043a\u043e\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435: \u0434\u043b\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u044b CPU \u043f\u044b\u0442\u0430\u0435\u0442\u0441\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u043a\u043e\u043c\u0430\u043d\u0434\u044b \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u043e, \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043e\u043c\u0430\u043d\u0434\u044b \u043d\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044d\u0442\u0430\u043f\u043e\u0432, \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c, F-D-E-W (fetch, decode, execute, writeback \u2014 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435, \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435, \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435, \u0437\u0430\u043f\u0438\u0441\u044c \u043e\u0431\u0440\u0430\u0442\u043d\u043e). \u041f\u0440\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u043c \u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u043e\u043d \u043c\u043e\u0436\u0435\u0442 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043d\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u044d\u0442\u0430\u043f\u0430\u0445 \u0440\u0430\u0437\u043d\u044b\u0445 \u043a\u043e\u043c\u0430\u043d\u0434 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440: \u043a\u043e\u043c\u0430\u043d\u0434\u0430 5 \u043d\u0430 \u044d\u0442\u0430\u043f\u0435 F, 6 \u2014 \u043d\u0430 \u044d\u0442\u0430\u043f\u0435 D, 7E, 8F). \u0422\u0440\u0443\u0434\u043d\u043e\u0441\u0442\u0438 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u044e\u0442 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0430\u043b\u0438\u0447\u0438\u044f \u0432 \u043a\u043e\u0434\u0435 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0439, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043a\u043e\u043c\u0430\u043d\u0434 \u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043d\u0435\u043a\u043e\u0433\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u043a\u043e\u043c\u0430\u043d\u0434\u043e\u0439 \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c X \u0438\u043b\u0438 Y. CPU <em>\u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u0443\u0435\u0442<\/em> \u043e\u0434\u0438\u043d \u0432\u0430\u0440\u0438\u0430\u043d\u0442, X, \u0438 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u043f\u043e\u044d\u0442\u0430\u043f\u043d\u043e\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435, \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044f \u044d\u0442\u0430\u043f\u044b, \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c, X+1 \u0438 X+2. \u041a\u043e\u0433\u0434\u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0431\u0443\u0434\u0435\u0442 \u0433\u043e\u0442\u043e\u0432, \u043d\u043e \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u043a\u043e\u043c\u0430\u043d\u0434\u0443 Y, \u0442\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f X, X+1 \u0438 X+2 \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u0431\u0435\u0441\u0441\u043c\u044b\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0438 \u0432\u044b\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u044e\u0442\u0441\u044f. \u041e\u0448\u0438\u0431\u043e\u0447\u043d\u044b\u0435 \u043f\u0440\u043e\u0433\u043d\u043e\u0437\u044b \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f \u0437\u0430\u0442\u0440\u0430\u0442\u043d\u044b, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 CPU \u043c\u043e\u0433 \u0432\u043c\u0435\u0441\u0442\u043e \u043d\u0438\u0445 \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0440\u0430\u0441\u0447\u0451\u0442\u044b Y, Y+1 \u0438 Y+2.<\/p>\n<p>  \u041f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0439 \u2014 \u043e\u0442\u043b\u0438\u0447\u043d\u0430\u044f \u0432\u0435\u0449\u044c, \u043d\u043e \u043d\u0435 \u0434\u043b\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430. \u042d\u0442\u043e \u043f\u043e\u0438\u0441\u043a, \u0430 \u0438\u0449\u0435\u043c \u043c\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e, \u043c\u0435\u0441\u0442\u043e\u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0447\u0435\u0433\u043e \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u0437\u043d\u0430\u0435\u043c, \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u044b \u0431\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u0437\u044f\u043b\u0438 \u043d\u0443\u0436\u043d\u043e\u0435. \u042d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0442\u043e <code>if (comp(first[half], value))<\/code> \u043d\u0435\u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0443\u0435\u043c\u043e \u043f\u0440\u0438 \u043e\u0431\u044b\u0447\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0438 <code>std::lower_bound<\/code>.<\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/4v\/b6\/b6\/4vb6b6w7jvbokzoxnihpxwxozyg.png\" data-src=\"https:\/\/habrastorage.org\/webt\/4v\/b6\/b6\/4vb6b6w7jvbokzoxnihpxwxozyg.png\"\/><\/div>\n<p><i><font color=\"#999999\">\u00ab\u041c\u043e\u0438 \u043f\u0440\u043e\u0433\u043d\u043e\u0437\u044b \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u0441\u043b\u0443\u0447\u0430\u0435\u0432!\u00bb<\/font><\/i><\/p>\n<p>  \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043c\u043e\u0436\u0435\u043c \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0443.<\/p>\n<p>  \u041c\u044b \u0433\u043e\u0432\u043e\u0440\u0438\u043c:<\/p>\n<pre><code class=\"cpp\">\/\/ bstd_lower_bound() auto length = last - first; while (length > 0) {    auto half = length \/ 2;    bool compare = comp(first[half], value);    \/\/ if \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0435\u0442    first = compare ? first + half + 1 : first;    length = compare ? length - half - 1 : half; } return first;<\/code><\/pre>\n<p>  \u041a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 Clang: \u00ab\u041d\u0435\u0442, \u044d\u0442\u043e \u0442\u0430\u043a \u043d\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442!\u00bb<\/p>\n<p>  \u041c\u044b: <code>-mllvm -x86-cmov-converter=false<\/code><\/p>\n<p>  \u041a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 Clang: \u00ab\u041a\u0430\u043a \u0441\u043a\u0430\u0436\u0435\u0442\u0435, \u0431\u043e\u0441\u0441\u00bb<sup><a href=\"#3\">3<\/a><\/sup>.<\/p>\n<p>  \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0430 25% \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0434\u0432\u0435 \u043a\u043e\u043c\u0430\u043d\u0434\u044b \u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0438. \u041d\u0435\u043f\u043b\u043e\u0445\u043e. \u041d\u043e \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e <code>-mllvm -x86-cmov-converter=false<\/code>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u043c \u0434\u043e <code>-cmov<\/code>, \u043d\u0430\u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0436\u0435 \u0443\u0441\u043a\u043e\u0440\u044f\u0435\u0442 <code>std::lower_bound<\/code>, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e clang \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0443\u043c\u0451\u043d, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c, \u043a\u0430\u043a \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u044c <code>if<\/code>\/<code>else<\/code> \u0432 \u0443\u0441\u043b\u043e\u0432\u043d\u0443\u044e \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0443. \u0423 gcc \u043d\u0435\u0442 \u0442\u0430\u043a\u043e\u0439 \u043e\u043f\u0446\u0438\u0438, \u0438 \u043e\u0431\u044b\u0447\u043d\u043e \u0435\u0433\u043e \u043d\u0435 \u0432\u043e\u043b\u043d\u0443\u0435\u0442, \u0447\u0442\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e.<\/p>\n<p>  \u0412 \u0446\u0435\u043b\u043e\u043c \u043f\u043e\u043a\u0430 \u043d\u0435\u0442 \u0443\u0434\u043e\u0431\u043d\u043e\u0433\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u0430 \u0443\u0437\u043d\u0430\u0442\u044c, \u0431\u0443\u0434\u0435\u0442 \u043b\u0438 clang<sup><a href=\"#4\">4<\/a><\/sup> \u0438\u043b\u0438 gcc<sup><a href=\"#5\">5<\/a><\/sup> \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0443\u0441\u043b\u043e\u0432\u043d\u0443\u044e \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0443 \u0432 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435. \u041d\u043e \u044f \u043f\u0438\u0448\u0443 \u0441\u0442\u0430\u0442\u044c\u044e \u043d\u0435 \u043e\u0431 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u044f\u0445 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u043e\u0432, \u0442\u0430\u043a \u0447\u0442\u043e \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0434\u0430\u043b\u044c\u0448\u0435.<\/p>\n<h2><font color=\"#3AC1EF\">\u0421 \u0447\u0435\u0433\u043e \u0432\u0441\u0451 \u043d\u0430\u0447\u0430\u043b\u043e\u0441\u044c<\/font><\/h2>\n<p>  \u041f\u043e\u0447\u0435\u043c\u0443 \u043c\u044b \u0432\u043e\u043e\u0431\u0449\u0435 \u043e\u0431\u0441\u0443\u0436\u0434\u0430\u0435\u043c \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u0435 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430? \u0417\u0430\u0447\u0435\u043c \u044f \u0432\u0442\u044f\u0433\u0438\u0432\u0430\u044e \u0432\u0430\u0441 \u0432 \u044d\u0442\u043e? \u041f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043c\u0435\u043d\u044f \u0441\u0430\u043c\u043e\u0433\u043e \u0432 \u044d\u0442\u043e \u0432\u0442\u044f\u043d\u0443\u043b\u0438.<\/p>\n<p>  \u042f \u0443\u0432\u0438\u0434\u0435\u043b, \u043a\u0430\u043a \u041c\u0430\u043b\u0442\u0435 \u0421\u043a\u0430\u0440\u0443\u043f\u043a\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0428\u043e\u0440\u0430 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u043d\u0430 C++ (<code>branchless_lower_bound<\/code>), \u0438 \u043d\u0435 \u043c\u043e\u0433 \u043e\u0442\u0434\u0435\u043b\u0430\u0442\u044c\u0441\u044f \u043e\u0442 \u043c\u044b\u0441\u043b\u0438, \u0447\u0442\u043e \u043e\u043d \u043d\u0435\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u0435\u043d. \u0412\u0435\u0440\u0441\u0438\u044f \u041c\u0430\u043b\u0442\u0435 \u0438\u043d\u043e\u0433\u0434\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u0442 <code>value<\/code> \u0441 \u043e\u0434\u043d\u0438\u043c \u0438 \u0442\u0435\u043c \u0436\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u0437\u0430\u0434\u0430\u043b\u0441\u044f \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u043c, \u043a\u0430\u043a\u0438\u043c \u0436\u0435 \u0431\u0443\u0434\u0435\u0442 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f? \u042d\u0442\u043e \u043f\u0440\u0438\u0432\u0435\u043b\u043e \u043c\u0435\u043d\u044f \u043a \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044e <code>sb_lower_bound<\/code>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043d\u0430 20% \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c <a href=\"https:\/\/probablydance.com\/2023\/04\/27\/beautiful-branchless-binary-search\/\">\u0432\u0435\u0440\u0441\u0438\u0438 lower_bound \u041c\u0430\u043b\u0442\u0435, \u043f\u043e \u0435\u0433\u043e \u0442\u0435\u0441\u0442\u0430\u043c \u043e\u043a\u0430\u0437\u0430\u0432\u0448\u0430\u044f\u0441\u044f \u0432\u0434\u0432\u043e\u0435 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0443 GCC<\/a>.<\/p>\n<p>  \u00ab\u0427\u0442\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u0442\u0430\u043a\u043e\u0435 \u201e\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439\u201c \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a?\u00bb \u0425\u043e\u0440\u043e\u0448\u0438\u0439 \u0432\u043e\u043f\u0440\u043e\u0441. \u0414\u0443\u043c\u0430\u044e, \u0447\u0442\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u00ab\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u0435\u043d\u00bb, \u0435\u0441\u043b\u0438 \u043e\u043d \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0437\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439. \u042d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u043e, \u0435\u0441\u043b\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f (\u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e) \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0430\u044f. \u041c\u0430\u043b\u0442\u0435 \u043e\u0442\u043c\u0435\u0442\u0438\u043b, \u0447\u0442\u043e \u0435\u0433\u043e \u0432\u0435\u0440\u0441\u0438\u044f \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c <code>std::lower_bound<\/code> \u043f\u0440\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0435 \u0432 \u0431\u043e\u043b\u044c\u0448\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u0441\u0442\u0440\u043e\u043a.<\/p>\n<p>  \u0412\u0437\u0433\u043b\u044f\u043d\u0443\u0432 \u043d\u0430 <code>std::lower_bound<\/code>, \u043c\u044b \u0443\u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u043e\u043d\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0438\u0442\u0435\u0440\u0430\u0442\u043e\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043e\u0436\u0435\u0442 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u043d\u0430 \u043b\u044e\u0431\u043e\u0439 \u0438\u0437 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441\u043f\u0438\u0441\u043a\u0430, \u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u043d\u0430 \u043e\u0434\u0438\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0437\u0430 \u0435\u0433\u043e \u043a\u043e\u043d\u0446\u043e\u043c. \u0414\u043b\u044f \u0441\u043f\u0438\u0441\u043a\u0430 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c <code>n<\/code> \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 <code>n+1<\/code> \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432. \u0422\u043e \u0435\u0441\u0442\u044c \u0434\u043b\u044f \u0441\u043f\u0438\u0441\u043a\u0430 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c <code>2<sup>k<\/sup>-1<\/code> \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 <code>2<sup>k<\/sup><\/code> \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432. \u0412 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0440\u0430\u0432\u043d\u043e <code>k<\/code>. \u042d\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0432\u0441\u0435\u043c\u0438 <code>2<sup>k<\/sup><\/code> \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430\u043c\u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 <code>k<\/code> \u0431\u0438\u0442\u043e\u0432 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438, \u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0434\u0430\u0451\u0442 \u043d\u0430\u043c 1 \u0431\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 (true \u0438\u043b\u0438 false). \u041f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0432 \u044d\u0442\u043e\u0442 \u0441\u043b\u0443\u0447\u0430\u0439 \u0432 \u043a\u043e\u0434, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c:<\/p>\n<pre><code class=\"cpp\">\/\/ \u041e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e, \u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442, \u043a\u043e\u0433\u0434\u0430 \u0434\u043b\u0438\u043d\u0430 \u0440\u0430\u0432\u043d\u0430 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438 \u043c\u0438\u043d\u0443\u0441 1 \/\/ \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u043a \u0434\u043e\u0441\u0442\u0443\u043f\u0443 out of bounds, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f \/\/ \u043c\u0430\u0441\u0441\u0438\u0432\u0430 [0, 1, 2, 3, 4, 5] \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f 4 auto length = last - first; while (length > 0) {    length \/= 2;    if (comp(first[length], value)) {       first += length + 1;    } } return first;<\/code><\/pre>\n<p>  \u041f\u0440\u0438 clang <code>-cmov<\/code> \u0446\u0438\u043a\u043b \u043a\u043e\u043c\u043f\u0438\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 6 \u043a\u043e\u043c\u0430\u043d\u0434, \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f <code>cmov<\/code>. \u042d\u0442\u043e\u0442 \u043a\u043e\u0434 (\u0438 \u043a\u043e\u0434 \u041c\u0430\u043b\u0442\u0435) \u043d\u0430\u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0431\u044b\u0441\u0442\u0440, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0435 <code>first<\/code>.<\/p>\n<h2><font color=\"#3AC1EF\">sb_lower_bound<\/font><\/h2>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c <code>sb_lower_bound<\/code> (\u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 \u0434\u0430\u043d\u043e \u043e\u0442 <em>simple branchless<\/em>, \u00ab\u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f\u00bb). \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u044f \u043d\u0430\u0442\u043a\u043d\u0443\u043b\u0441\u044f \u043d\u0430 \u043d\u0435\u0433\u043e \u043f\u043e\u0437\u0436\u0435, \u0447\u0435\u043c \u043d\u0430 \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u044b\u0435 \u0432\u0435\u0440\u0441\u0438\u0438 (\u043e \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u0430\u043d\u043e \u043d\u0438\u0436\u0435), \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043d \u043d\u0435 \u00ab\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u0435\u043d\u00bb.<\/p>\n<pre><code class=\"cpp\">auto length = last - first; while (length > 0) {    auto rem = length % 2;    length \/= 2;    if (comp(first[length], value)) {       first += length + rem;    } } return first;<\/code><\/pre>\n<p>  \u041a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437, \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u0440\u0430\u0437\u0431\u0438\u0432\u0430\u0435\u043c \u0441\u043f\u0438\u0441\u043e\u043a, \u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0447\u0451\u0442\u043d\u044b\u043c, \u0430 comp \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 true, \u0442\u043e \u043c\u044b \u043d\u0435 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0414\u043b\u044f <code>n<\/code> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0433\u0434\u0435 <code>2<sup>k<\/sup> &lt;= n &lt; 2<sup>k+1<\/sup><\/code> \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c <code>sb_lower_bound<\/code> \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c <code>k+1<\/code> \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439, \u0430 <code>std::lower_bound<\/code> \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0438\u043b\u0438 <code>k<\/code>, \u0438\u043b\u0438 <code>k+1<\/code> \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439. \u0412 \u0441\u0440\u0435\u0434\u043d\u0435\u043c <code>std::lower_bound<\/code> \u0431\u0443\u0434\u0435\u0442 \u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e <code>log2(n+1)<\/code> \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439. \u0412 \u0446\u0435\u043b\u043e\u043c <code>sb_lower_bound<\/code> \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0443 \u043d\u0435\u0433\u043e \u0432 \u0446\u0438\u043a\u043b\u0435 \u0433\u043e\u0440\u0430\u0437\u0434\u043e \u043c\u0435\u043d\u044c\u0448\u0435 \u043a\u043e\u043c\u0430\u043d\u0434. \u0427\u0442\u043e\u0431\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 <code>k+1<\/code> \u0438 <code>log2(n+1)<\/code> \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c, \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0439.<\/p>\n<p>  \u0412\u0442\u043e\u0440\u0430\u044f \u0442\u043e\u043d\u043a\u043e\u0441\u0442\u044c \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0441\u0435\u0439\u0447\u0430\u0441 \u0432\u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0443\u0440\u043e\u0432\u043d\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 gcc \u043d\u0435 \u0441\u043e\u0437\u0434\u0430\u0451\u0442 \u0434\u043b\u044f <code>sb_lower_bound<\/code> \u043a\u043e\u0434 \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f. \u0414\u043b\u044f <code>std::lower_bound<\/code> \u043e\u043d \u0442\u043e\u0436\u0435 \u043d\u0435 \u0441\u043e\u0437\u0434\u0430\u0451\u0442 \u043a\u043e\u0434 \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c \u0438\u0442\u043e\u0433\u0435 \u043e\u043d \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u0442\u043e\u043b\u044c \u0436\u0435 \u0431\u044b\u0441\u0442\u0440\u044b\u043c. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0439 \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0439 \u043a\u043e\u0434, \u0447\u0442\u043e\u0431\u044b \u0432\u044b\u043d\u0443\u0434\u0438\u0442\u044c gcc \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c <code>cmov<\/code>, \u043d\u043e \u0442\u0443\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u043a. \u041f\u0440\u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u044c\u0448\u0435 \u043a\u043e\u043c\u0430\u043d\u0434, \u0447\u0435\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e. \u0410\u043b\u044c\u0442\u0435\u0440\u043d\u0430\u0442\u0438\u0432\u0430 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0440\u0430\u0437\u043d\u043e\u0433\u043e \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u043e\u0433\u043e \u043a\u043e\u0434\u0430 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430 <code>value<\/code> (int, float \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435).<\/p>\n<pre><code class=\"cpp\">auto length = last - first; while (length > 0) {    auto rem = length % 2;    length \/= 2;    auto firstplus = first + length + rem;    \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435, \u0437\u0430\u0434\u0430\u044e\u0449\u0438\u0435 x86 FLAGS \u043d\u0430\u043f\u043e\u0434\u043e\u0431\u0438\u0435 CF \u0438\u043b\u0438 ZF    bool compare = comp(first[length], value);    \/\/ \u0412\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0439 \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0439 \u043a\u043e\u0434 \u043d\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0443 bool \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u0432\u043e FLAGS    \/\/ \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u044b \u043f\u0440\u043e\u0441\u0438\u043c \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 \u0441\u043a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u0445 \u0438\u0437 FLAGS \u0432 \u0440\u0435\u0433\u0438\u0441\u0442\u0440    __asm__(          \/\/ \u0417\u0430\u0442\u0435\u043c \u043c\u044b \u0442\u0435\u0441\u0442\u0438\u0440\u0443\u0435\u043c \u0440\u0435\u0433\u0438\u0441\u0442\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u0442 ZF=!compare \u0438 CF=0          \/\/ \u0421\u0441\u044b\u043b\u043a\u0430: https:\/\/www.felixcloutier.com\/x86\/test          \"test %[compare],%[compare]\\n\"          \/\/ cmova \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u0442 firstplus first, \u0435\u0441\u043b\u0438 ZF=0 \u0438 CF=0          \/\/ \u0421\u0441\u044b\u043b\u043a\u0430: https:\/\/www.felixcloutier.com\/x86\/cmovv          \"cmova %[firstplus],%[first]\\n\"          : [first] \"+r\"(first)          : [firstplus] \"r\"(firstplus), [compare]\"r\"(compare)    ); } return first;<\/code><\/pre>\n<p>  \u0412 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c gcc-\u0432\u0435\u0440\u0441\u0438\u044f <code>std::lower_bound<\/code>, \u043d\u043e \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c <code>sb_lower_bound<\/code> \u0441 clang <code>-cmov<\/code>. \u041f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043b\u044f \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0430\u0446\u0438\u0438.<\/p>\n<h2><font color=\"#3AC1EF\">\u258d \u0411\u043e\u043b\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e<\/font><\/h2>\n<p>  \u0412\u043e \u0432\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u044f \u043e\u0431\u0435\u0449\u0430\u043b \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u0435\u0449\u0451 \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u0443\u044e \u0432\u0435\u0440\u0441\u0438\u044e. \u0412\u043e\u0442 \u043e\u043d\u0430:<\/p>\n<pre><code class=\"cpp\">\/\/ bb_lower_bound auto length = last - first; \/\/ \u043f\u043e\u043a\u0430 length \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e \u0434\u0432\u043e\u0439\u043a\u0438 \u043c\u0438\u043d\u0443\u0441 1 while (length &amp; (length + 1)) {    auto step = length \/ 8 * 6 + 1; \/\/ \u041c\u0410\u0413\u0418\u042f    if (comp(first[step], value)) {       first += step + 1;       length -= step + 1;    } else {       length = step;       break;    } } while (length != 0) {    length \/= 2;    if (comp(first[length], value)) {       first += length + 1;    } } return first;<\/code><\/pre>\n<p>  \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u043a\u0440\u0430\u0442\u0446\u0435 \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c <code>length &amp; (length + 1)<\/code>. \u041f\u0440\u0438\u043c\u0435\u0440: <code>length<\/code> \u0440\u0430\u0432\u043d\u0430 <code>110011<\/code>, <code>length+1<\/code> \u0440\u0430\u0432\u043d\u0430 <code>110100<\/code>, <code>length &amp; (length+1)<\/code> \u0440\u0430\u0432\u043d\u043e <code>110000<\/code>. \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u043e\u043d\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 \u0438\u043c\u0435\u044e\u0442 \u043e\u0434\u0438\u043d \u043e\u0431\u0449\u0438\u0439 \u0441\u0430\u043c\u044b\u0439 \u0441\u0442\u0430\u0440\u0448\u0438\u0439 \u0431\u0438\u0442 <code>1<\/code>, \u0437\u0430 \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u044f, \u043a\u043e\u0433\u0434\u0430 <code>length+1<\/code> \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043f\u0435\u0440\u0435\u043d\u043e\u0441 \u0432\u0441\u0435\u0445 \u0431\u0438\u0442\u043e\u0432 \u0441\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c 1. \u042d\u0442\u043e \u0441\u043b\u0443\u0447\u0430\u0439, \u043a\u043e\u0433\u0434\u0430 <code>length<\/code> \u0438\u043c\u0435\u0435\u0442 \u0432\u0438\u0434 <code>11..1<\/code>, \u0442\u043e \u0435\u0441\u0442\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0434\u0432\u043e\u0439\u043a\u0438 \u043c\u0438\u043d\u0443\u0441 1, \u0438 \u0432 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <code>length &amp; (length + 1)<\/code> \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u043e 0. \u042d\u0442\u0430 \u043c\u0435\u0442\u043e\u0434\u0438\u043a\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0430\u0434\u0430\u043f\u0442\u0430\u0446\u0438\u0435\u0439 \u043e\u0434\u043d\u043e\u0433\u043e \u0438\u0437 \u0442\u0440\u044e\u043a\u043e\u0432 \u0441 \u0436\u043e\u043d\u0433\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0431\u0438\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u043f\u043e\u043c\u043d\u044e. \u041e\u0441\u0442\u043e\u0440\u043e\u0436\u043d\u043e, \u0437\u0434\u0435\u0441\u044c \u0435\u0441\u0442\u044c <a href=\"https:\/\/graphics.stanford.edu\/~seander\/bithacks.html\">\u0446\u0435\u043b\u0430\u044f \u043a\u0443\u0447\u0430 \u043f\u043e\u0442\u0440\u044f\u0441\u0430\u044e\u0449\u0438\u0445 \u0442\u0440\u044e\u043a\u043e\u0432<\/a>.<\/p>\n<p>  \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c length \u00ab\u0445\u043e\u0440\u043e\u0448\u0435\u0439\u00bb, \u0435\u0441\u043b\u0438 \u043e\u043d\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e \u0434\u0432\u043e\u0439\u043a\u0438 \u043c\u0438\u043d\u0443\u0441 1. \u0412\u044b\u0448\u0435 \u043c\u044b \u0432\u044b\u044f\u0441\u043d\u0438\u043b\u0438, \u0447\u0442\u043e \u0434\u043b\u044f \u0445\u043e\u0440\u043e\u0448\u0438\u0445 \u0434\u043b\u0438\u043d \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a. \u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u043b\u0430\u0441\u044c \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0435\u0443\u0434\u043e\u0431\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043c\u044b \u0431\u044b \u0440\u0430\u0437\u0431\u0438\u0432\u0430\u043b\u0438 \u0441\u043f\u0438\u0441\u043e\u043a \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0435 \u043f\u043e\u043f\u043e\u043b\u0430\u043c, \u0430 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0431\u044b\u0441\u0442\u0440\u043e \u043f\u0440\u0438\u0439\u0442\u0438 \u043a \u043f\u043e\u0438\u0441\u043a\u0443 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e \u043f\u043e\u0434\u0441\u043f\u0438\u0441\u043a\u0430\u043c \u0445\u043e\u0440\u043e\u0448\u0435\u0439 \u0434\u043b\u0438\u043d\u044b. \u042d\u0442\u0430 \u0438\u0434\u0435\u044f \u0431\u044b\u043b\u0430 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e\u0439, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043d\u0430\u043c \u0431\u044b \u043f\u0440\u0438\u0448\u043b\u043e\u0441\u044c \u0442\u0440\u0430\u0442\u0438\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u0441\u043f\u0438\u0441\u043a\u0430. \u041f\u0435\u0440\u0432\u044b\u0439 \u043a\u043e\u043c\u043f\u0440\u043e\u043c\u0438\u0441\u0441 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u044d\u0442\u043e\u043c \u0440\u0430\u043d\u043d\u0435\u043c <code>break<\/code>, \u043e\u0437\u043d\u0430\u0447\u0430\u044e\u0449\u0435\u043c, \u0447\u0442\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u0446\u0438\u043a\u043b <code>while<\/code> \u043c\u043e\u0436\u0435\u0442 (\u043d\u0435\u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e) \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u043c\u0438 \u0441\u0432\u043e\u0435\u0439 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b; \u043d\u043e \u0434\u043e\u0441\u0442\u0443\u043f out of bounds \u043d\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u044d\u0442\u043e\u0442 \u043f\u043e\u0434\u0441\u043f\u0438\u0441\u043e\u043a \u043d\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430. \u042d\u0442\u043e\u0442 \u043a\u043e\u043c\u043f\u0440\u043e\u043c\u0438\u0441\u0441 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a\u043e \u0432\u0442\u043e\u0440\u043e\u043c\u0443 \u043a\u043e\u043c\u043f\u0440\u043e\u043c\u0438\u0441\u0441\u0443, \u043d\u043e \u041c\u0410\u0413\u0418\u042f \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0432\u044b\u0431\u043e\u0440\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 <code>step<\/code>. \u0414\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f <code>step<\/code> \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u043c, \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e <code>>= length\/2<\/code>, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043c\u044b \u0447\u0430\u0449\u0435 \u0432\u044b\u0445\u043e\u0434\u0438\u043c \u043a \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u043c\u0443 \u0446\u0438\u043a\u043b\u0443 <code>while<\/code>. \u041d\u043e \u043d\u0435 \u043d\u0430\u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043c, \u0447\u0442\u043e\u0431\u044b <code>step<\/code> \u0431\u044b\u043b \u043f\u043e\u0447\u0442\u0438 \u0440\u0430\u0432\u0435\u043d <code>length<\/code>, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043c\u044b \u043f\u043e\u0442\u0435\u0440\u044f\u0435\u043c \u0442\u043e, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0431\u044b\u0441\u0442\u0440\u044b\u043c. \u0422\u0430\u043a\u0436\u0435 \u043c\u044b \u0431\u044b \u043f\u0440\u0435\u0434\u043f\u043e\u0447\u043b\u0438, \u0447\u0442\u043e\u0431\u044b <code>step<\/code> \u0431\u044b\u043b \u00ab\u0445\u043e\u0440\u043e\u0448\u0438\u043c\u00bb \u0438\u043b\u0438 \u0438\u043c\u0435\u043b \u043c\u043d\u043e\u0433\u043e \u0435\u0434\u0438\u043d\u0438\u0446 \u0432 \u0441\u0432\u043e\u0451\u043c \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u0432\u0438\u0434\u0435, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0432\u0442\u043e\u0440\u043e\u0439 \u0446\u0438\u043a\u043b <code>while<\/code> \u0431\u043e\u043b\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c. \u0418\u043c\u0435\u043d\u043d\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0435\u0434\u0438\u043d\u0438\u0446 \u0437\u0430\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>step<\/code> \u0431\u044b\u0442\u044c \u043d\u0435\u0447\u0451\u0442\u043d\u044b\u043c. \u0418 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435: \u043c\u044b \u0445\u043e\u0442\u0438\u043c, \u0447\u0442\u043e\u0431\u044b <code>length - step - 1<\/code> \u0431\u044b\u043b\u043e \u00ab\u0445\u043e\u0440\u043e\u0448\u0438\u043c\u00bb.<\/p>\n<p>  \u042f \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043c\u043d\u043e\u0433\u043e \u0432\u0430\u0440\u0438\u0430\u0446\u0438\u0439. \u0421\u0430\u043c\u043e\u0439 \u043f\u0440\u0438\u0432\u043b\u0435\u043a\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0431\u044b\u043b\u0430 <code>auto step = length >> 1; step |= step >> 1;<\/code>; \u044f \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u043b, \u0447\u0442\u043e \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0445\u043e\u0440\u043e\u0448\u0430\u044f \u0431\u044b\u0441\u0442\u0440\u0430\u044f \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0430, \u0431\u0430\u043b\u0430\u043d\u0441\u0438\u0440\u0443\u044e\u0449\u0430\u044f \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u0432\u044b\u0448\u0435 \u043a\u043e\u043c\u043f\u0440\u043e\u043c\u0438\u0441\u0441\u044b, \u043e\u043d\u0430 \u043e\u0447\u0435\u043d\u044c \u0431\u043b\u0438\u0437\u043a\u0430 \u043a \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439, \u043d\u043e \u0432 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c \u0438\u0442\u043e\u0433\u0435 \u043e\u043a\u0430\u0437\u0430\u043b\u0430\u0441\u044c \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u041c\u0410\u0413\u0418\u0418. \u0415\u0449\u0451 \u043e\u0434\u043d\u0430 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0438\u0437 \u00abbreak\u00bb \u0432 \u043d\u0435\u0439 \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0435.<\/p>\n<p>  \u0415\u0449\u0451 \u043e\u0434\u043d\u0430 \u043d\u0435\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u043f\u043e\u043b\u043d\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0435 \u0441\u0430\u043c\u044b\u0445 \u0431\u044b\u0441\u0442\u0440\u044b\u0445 (\u043d\u043e \u0432\u0441\u0451 \u0440\u0430\u0432\u043d\u043e \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445) \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 <code>step<\/code> \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u0438 \u0432 \u0441\u043e\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u0438 \u0438\u0445 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443. \u041f\u043e\u0442\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0438\u0437\u0432\u043b\u0435\u0447\u044c \u0438\u0437 \u044d\u0442\u043e\u0439 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0445\u043e\u0440\u043e\u0448\u0443\u044e \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0443, \u0438\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0435\u0451 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e. \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u0441 <code>sb_lower_bound<\/code> \u044f \u043d\u0430\u0448\u0451\u043b \u0441\u0432\u043e\u044e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0445\u043e\u0440\u043e\u0448\u0443\u044e \u0442\u043e\u0447\u043a\u0443, \u043d\u043e \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u0432\u043e\u043f\u0440\u043e\u0441 \u0433\u043b\u0443\u0431\u0436\u0435.<\/p>\n<pre><code class=\"cpp\">auto length = last - first; while (length &amp; (length + 1)) {    auto step = precomputed[length];    if (comp(first[step], value)) {       first += step + 1;       length -= step + 1;    } else {       length = step;    } }<\/code><\/pre>\n<p>  <\/p>\n<h2><font color=\"#3AC1EF\">\u0427\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0439, \u0442\u0435\u043c \u043b\u0443\u0447\u0448\u0435?<\/font><\/h2>\n<p>  \u0415\u0441\u043b\u0438 \u0432\u043a\u0440\u0430\u0442\u0446\u0435, \u0442\u043e \u043d\u0435\u0442. \u042d\u0442\u043e\u0442 \u0440\u0430\u0437\u0434\u0435\u043b \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c, \u043d\u043e \u0432\u043e\u0442 \u0431\u043e\u043b\u0435\u0435 \u0440\u0430\u0437\u0432\u0451\u0440\u043d\u0443\u0442\u044b\u0439 \u043e\u0442\u0432\u0435\u0442: \u0434\u043b\u044f <code>n<\/code> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0433\u0434\u0435 <code>2<sup>k<\/sup> &lt;= n &lt; 2<sup>k+1<\/sup><\/code>, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c <code>sb_lower_bound<\/code> \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c <code>k+1<\/code> \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439. \u041d\u0430 64-\u0431\u0438\u0442\u043d\u043e\u0439 \u043c\u0430\u0448\u0438\u043d\u0435 \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c 64 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439 \u0446\u0438\u043a\u043b\u0430 <code>while (length > 0)<\/code>. \u0422\u043e \u0435\u0441\u0442\u044c \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0432\u0435\u0440\u0441\u0438\u044e \u00ab\u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f\u00bb, \u043d\u0435 \u0438\u043c\u0435\u044e\u0449\u0443\u044e \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 <code>length<\/code> \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u043d\u0430\u043c\u0435\u0440\u0435\u043d\u043d\u043e \u043d\u0435\u0443\u0434\u0430\u0447\u043d\u043e\u043c\u0443 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044e <code>switch<\/code>.<\/p>\n<pre><code class=\"cpp\">size_t length = last - first; size_t rem; switch(std::bit_width(length)) {    case 64:       rem = length % 2;       length \/= 2;       first += comp(first[length], value) * (length + rem);    case 63:       rem = length % 2;       length \/= 2;       first += comp(first[length], value) * (length + rem);    \/\/ ...    case 1:       rem = length % 2;       length \/= 2;       first += comp(first[length], value) * (length + rem); } return first;<\/code><\/pre>\n<p>  \u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u043d\u0435\u0437\u043d\u0430\u043a\u043e\u043c <code>switch<\/code>, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0441\u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u0435\u0433\u043e \u043a\u0430\u043a \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u0432 \u043a\u043e\u0434. \u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u0442\u043e \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043c\u044b \u0434\u0435\u043b\u0430\u0435\u043c \u0440\u043e\u0432\u043d\u043e \u043d\u0443\u0436\u043d\u043e\u0435 \u043d\u0430\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439.<\/p>\n<p>  \u00ab\u0411\u044b\u0441\u0442\u0440\u0435\u0435 \u043b\u0438 \u043e\u043d?\u00bb \u041d\u0435\u0442. \u0421\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u044b x86 \u0445\u043e\u0440\u043e\u0448\u043e \u0441\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c\u0438 \u0446\u0438\u043a\u043b\u043e\u0432, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043d\u0438 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0443\u0435\u043c\u044b; \u043a\u0440\u0430\u0439\u043d\u0435 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u0432 \u0446\u0438\u043a\u043b\u0435. \u0418 \u044d\u0442\u043e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0445\u043e\u0440\u043e\u0448\u043e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u043c \u043d\u0435 \u043f\u0438\u0441\u0430\u0442\u044c \u0448\u0430\u0431\u043b\u043e\u043d\u044b \u0438\u043b\u0438 \u043c\u0430\u043a\u0440\u043e\u0441\u044b \u0438 \u043d\u0435 \u043a\u043e\u043f\u0438\u043f\u0430\u0441\u0442\u0438\u0442\u044c \u0438 \u0440\u0435\u0434\u0430\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u043e\u0434 \u0434\u043b\u044f 64 \u0441\u043b\u0443\u0447\u0430\u0435\u0432.<\/p>\n<h2><font color=\"#3AC1EF\">\u0412\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043a \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438<\/font><\/h2>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/rr\/3x\/64\/rr3x64en6bgsfzindyu9zxnu8yk.png\" data-src=\"https:\/\/habrastorage.org\/webt\/rr\/3x\/64\/rr3x64en6bgsfzindyu9zxnu8yk.png\"\/><\/div>\n<p>  \u0421\u0440\u0435\u0434\u043d\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f (\u043d\u0441):<\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th><\/th>\n<th><code>std::lower_<\/code><\/th>\n<th align=\"center\"><code>branchless_lower_<\/code><\/th>\n<th align=\"center\"><code>asm_lower_<\/code><\/th>\n<th align=\"center\"><code>sb_lower_<\/code><\/th>\n<th align=\"center\"><code>sbm_lower_<\/code><\/th>\n<th align=\"center\"><code>bb_lower_<\/code><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>gcc<\/td>\n<td align=\"center\">80.68<\/td>\n<td align=\"center\">43.65<\/td>\n<td align=\"center\">54.92<\/td>\n<td align=\"center\">77.22<\/td>\n<td align=\"center\">34.19<\/td>\n<td align=\"center\">75.64<\/td>\n<\/tr>\n<tr>\n<td>clang<\/td>\n<td align=\"center\">78.66<\/td>\n<td align=\"center\">90.97<\/td>\n<td align=\"center\">51.83<\/td>\n<td align=\"center\">80.06<\/td>\n<td align=\"center\">83.95<\/td>\n<td align=\"center\">74.44<\/td>\n<\/tr>\n<tr>\n<td>clang -cmov<\/td>\n<td align=\"center\">61.30<\/td>\n<td align=\"center\">43.43<\/td>\n<td align=\"center\">54.32<\/td>\n<td align=\"center\"><strong>33.24<\/strong><\/td>\n<td align=\"center\">35.54<\/td>\n<td align=\"center\"><strong>32.73<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  \u0421\u0440\u0435\u0434\u043d\u0435\u0435 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f (\u043d\u0441):<\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th><\/th>\n<th align=\"center\"><code>std::lower_<\/code><\/th>\n<th align=\"center\"><code>branchless_lower_<\/code><\/th>\n<th align=\"center\"><code>asm_lower_<\/code><\/th>\n<th align=\"center\"><code>sb_lower_<\/code><\/th>\n<th align=\"center\"><code>sbm_lower_<\/code><\/th>\n<th align=\"center\"><code>bb_lower_<\/code><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>gcc<\/td>\n<td align=\"center\">62.44<\/td>\n<td align=\"center\">25.55<\/td>\n<td align=\"center\">32.35<\/td>\n<td align=\"center\">59.67<\/td>\n<td align=\"center\">20.62<\/td>\n<td align=\"center\">57.93<\/td>\n<\/tr>\n<tr>\n<td>clang<\/td>\n<td align=\"center\">61.24<\/td>\n<td align=\"center\">65.72<\/td>\n<td align=\"center\">30.67<\/td>\n<td align=\"center\">63.59<\/td>\n<td align=\"center\">66.91<\/td>\n<td align=\"center\">58.19<\/td>\n<\/tr>\n<tr>\n<td>clang -cmov<\/td>\n<td align=\"center\">39.17<\/td>\n<td align=\"center\">25.14<\/td>\n<td align=\"center\">31.21<\/td>\n<td align=\"center\"><strong>19.81<\/strong><\/td>\n<td align=\"center\">20.91<\/td>\n<td align=\"center\">21.33<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>  \u0412\u0440\u0435\u043c\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0432 \u0432\u0438\u0434\u0435 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u0438\u043a\u043e\u0432:<\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/s0\/mp\/j5\/s0mpj5nfcn1lrqfw1k3yt56f4b8.png\" data-src=\"https:\/\/habrastorage.org\/webt\/s0\/mp\/j5\/s0mpj5nfcn1lrqfw1k3yt56f4b8.png\"\/><\/div>\n<p>  \u00ab\u0427\u0442\u043e \u0437\u0430 <code>sbm_lower_bound<\/code>?\u00bb \u041f\u043e \u0441\u0443\u0442\u0438 \u044d\u0442\u043e <code>sb_lower_bound<\/code>, \u043d\u043e \u0438\u0437\u043c\u0435\u043d\u0451\u043d\u043d\u044b\u0439 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0445\u0438\u0442\u0440\u043e\u0441\u0442\u044c\u044e \u0437\u0430\u0441\u0442\u0430\u0432\u0438\u0442\u044c gcc \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0443\u0441\u043b\u043e\u0432\u043d\u0443\u044e \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0443. \u0420\u0430\u0437\u043d\u0438\u0446\u0430 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0437\u0430\u043c\u0435\u043d\u0435 \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440\u0430 <code>if<\/code> \u043d\u0430 <code>first += comp(first[length], value) * (length + rem)<\/code>. \u0422\u0430\u043a\u043e\u0439 \u043f\u0440\u0438\u0451\u043c \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441 \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u043e\u0440\u043e\u0436\u043d\u043e\u0441\u0442\u044f\u043c\u0438 \u0438 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u043c\u0438, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0432 \u043d\u043e\u0432\u043e\u0439 \u0432\u0435\u0440\u0441\u0438\u0438 gcc \u044d\u0442\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0438 \u043d\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c.<\/p>\n<p>  \u041a\u043e\u043c\u0430\u043d\u0434\u044b \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u043e\u0432, \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0438\u0440\u0443\u044e\u0449\u0438\u0435 \u043e\u043f\u0446\u0438\u0438 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430:<\/p>\n<pre><code class=\"cmake\">g++-10 -std=c++20 -Wall -O2 -march=haswell test.cpp -o test &amp;&amp; .\/test clang++-10 -std=c++20 -Wall -O2 -march=haswell test.cpp -o test &amp;&amp; .\/test clang++-10 -std=c++20 -Wall -O2 -march=haswell -mllvm -x86-cmov-converter=false test.cpp -o test &amp;&amp; .\/test<\/code><\/pre>\n<p>  <code>-march=native<\/code> \u0438 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0435 <code>-march<\/code> \u043d\u0435\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0432\u043b\u0438\u044f\u044e\u0442 \u043d\u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b. \u0411\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438 \u0437\u0430\u043c\u0435\u0440\u044f\u043b\u0438\u0441\u044c \u043d\u0430 intel i7 kaby lake.<\/p>\n<h3><font color=\"#3AC1EF\">\u258d \u041e\u0448\u0438\u0431\u043a\u0438 \u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0439<\/font><\/h3>\n<p>  \u0418\u0437\u0443\u0447\u0438\u0442\u044c \u043e\u0448\u0438\u0431\u043a\u0438 \u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f\/\u043f\u0440\u043e\u043c\u0430\u0445\u0438 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 <code>perf<\/code>:<\/p>\n<pre><code class=\"cmake\"># clang perf stat .\/test # [..]          16,599.95 msec task-clock:u     #    \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0430 1000 CPU # [..]     30,309,755,516      instructions:u   #    0.53  \u043a\u043e\u043c\u0430\u043d\u0434\u044b \u043d\u0430 \u0442\u0430\u043a\u0442      6,941,783,502      branches:u       #  418.181 \u041c\/\u0441      1,203,569,540      branch-misses:u  #   17.34% \u043e\u0442 \u0432\u0441\u0435\u0445 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0439 # clang -cmov perf stat .\/test # [..]          10,982.97 msec task-clock:u     #    \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0430 1000 CPU # [..]     32,603,123,521      instructions:u   #    0.90  \u043a\u043e\u043c\u0430\u043d\u0434\u044b \u043d\u0430 \u0442\u0430\u043a\u0442      4,070,883,093      branches:u       #  370.654 \u041c\/\u0441         35,954,999      branch-misses:u  #    0.88% \u043e\u0442 \u0432\u0441\u0435\u0445 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0439<\/code><\/pre>\n<p>  <code>-cmov<\/code> \u0443\u0441\u0442\u0440\u0430\u043d\u044f\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e 2,9 \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0439 \u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e 1,2 \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430 \u043f\u0440\u043e\u043c\u0430\u0445\u043e\u0432 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0439, \u0442\u043e \u0435\u0441\u0442\u044c \u0443\u0441\u0442\u0440\u0430\u043d\u044f\u0435\u0442 \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u043e \u0441\u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0432 41% \u0441\u043b\u0443\u0447\u0430\u0435\u0432 \u0432\u0435\u0442\u0432\u0438. \u042d\u0442\u043e \u0431\u043b\u0438\u0437\u043a\u043e \u043a 50%, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0431\u044b \u043c\u044b \u043e\u0436\u0438\u0434\u0430\u043b\u0438 \u043f\u0440\u0438 \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u043d\u0435\u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0443\u0435\u043c\u043e\u043c \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0438, \u043f\u0440\u0438 \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e\u0439 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0441\u0442\u0438 \u0438 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0430\u0445. \u0412 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <code>-cmov<\/code> \u043f\u0440\u0438\u0432\u0451\u043b \u0431\u044b \u0435\u0449\u0451 \u043a \u0431\u043e\u043b\u0435\u0435 \u0432\u044b\u0441\u043e\u043a\u0438\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f\u043c \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u0439.<\/p>\n<h3><font color=\"#3AC1EF\">\u258d \u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0438 \u0431\u043e\u043b\u0435\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0439 comp()<\/font><\/h3>\n<p>  \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0440\u0435\u0430\u043b\u0438\u0441\u0442\u0438\u0447\u043d\u044b\u0445 \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u0435\u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0441 \u0431\u043e\u043b\u0435\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 <code>comp()<\/code> \u043c\u043e\u0436\u043d\u043e \u0432\u0437\u044f\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u0440\u043e\u0432, \u0442\u0435\u043b\u0435\u0444\u043e\u043d\u043d\u044b\u0445 \u043d\u043e\u043c\u0435\u0440\u043e\u0432, \u0430\u043a\u043a\u0430\u0443\u043d\u0442\u043e\u0432 \u0438 \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0445 \u0441\u043b\u043e\u0432. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043b\u0441\u044f \u043d\u0430 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 8-\u0431\u0430\u0439\u0442\u043d\u044b\u043c\u0438 \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438.<\/p>\n<p>  \u0421\u0440\u0435\u0434\u043d\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f (\u043d\u0441):<\/p>\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th><\/th>\n<th align=\"center\"><code>std::lower_<\/code><\/th>\n<th align=\"center\"><code>branchless_lower_<\/code><\/th>\n<th align=\"center\"><code>sb_lower_<\/code><\/th>\n<th align=\"center\"><code>sbm_lower_<\/code><\/th>\n<th align=\"center\"><code>bb_lower_<\/code><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>gcc<\/td>\n<td align=\"center\"><strong>160.01<\/strong><\/td>\n<td align=\"center\">205.24<\/td>\n<td align=\"center\">165.66<\/td>\n<td align=\"center\">193.96<\/td>\n<td align=\"center\">163.91<\/td>\n<\/tr>\n<tr>\n<td>clang<\/td>\n<td align=\"center\"><strong>157.71<\/strong><\/td>\n<td align=\"center\">178.77<\/td>\n<td align=\"center\">162.68<\/td>\n<td align=\"center\">166.00<\/td>\n<td align=\"center\"><strong>157.22<\/strong><\/td>\n<\/tr>\n<tr>\n<td>clang -cmov<\/td>\n<td align=\"center\"><strong>156.06<\/strong><\/td>\n<td align=\"center\">193.70<\/td>\n<td align=\"center\">164.71<\/td>\n<td align=\"center\">181.57<\/td>\n<td align=\"center\">157.48<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p>\u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <code>std::lower_bound<\/code> \u043e\u0447\u0435\u043d\u044c \u043d\u0435\u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043d\u043e \u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c <code>sb_lower_bound<\/code>. \u0427\u0442\u043e\u0431\u044b \u0432\u0441\u0435\u0433\u0434\u0430 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0442\u044c \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0443\u044e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u0438 \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u043d\u044b\u043c\u0438 \u0442\u0438\u043f\u0430\u043c\u0438 <code>sb_lower_bound<\/code>, \u0430 \u0432\u043e \u0432\u0441\u0435\u0445 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c <code>std::lower_bound<\/code>.<\/p>\n<h2><font color=\"#3AC1EF\">\u0410\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0439 \u043a\u043e\u0434<\/font><\/h2>\n<p>  \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0431\u043b\u0438\u0437\u043a\u043e\u0433\u043e \u043a \u0436\u0435\u043b\u0435\u0437\u0443 \u043a\u043e\u0434\u0430 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c\u0441\u044f \u0437\u0430\u0432\u0435\u0440\u0448\u0451\u043d\u043d\u043e\u0439 \u0431\u0435\u0437 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u043e\u0433\u043e \u043a\u043e\u0434\u0430. \u0412\u043f\u0440\u043e\u0447\u0435\u043c, \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u0441\u043f\u043e\u043a\u043e\u0439\u043d\u043e \u043f\u0440\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u0440\u0430\u0437\u0434\u0435\u043b.<\/p>\n<pre><code class=\"cpp\">\u0412\u0440\u0435\u043c\u044f% |      \u043a\u043e\u043c\u0430\u043d\u0434\u044b  \/\/ std::lower_bound, clang -cmov, \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0439 \u043a\u043e\u0434 \u0441\u0430\u043c\u043e\u0433\u043e \u0433\u043e\u0440\u044f\u0447\u0435\u0433\u043e \u0446\u0438\u043a\u043b\u0430  1.68 \u250220:   mov      %rsi,%rcx             \/\/ rcx = length  3.20 \u2502      shr      %rcx                  \/\/ rcx = length \/ 2  1.08 \u2502      mov      %rcx,%rdx             \/\/ rdx = length \/ 2  4.42 \u2502      not      %rdx                  \/\/ rdx = binary_not(rdx) = -length \/ 2 - 1  2.85 \u2502      add      %rsi,%rdx             \/\/ rdx = length - length \/ 2 - 1 63.41 \u2502      vucomiss (%rax,%rcx,4),%xmm0   \/\/ \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c first[rcx] \u0441 value, \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c FLAGS  0.21 \u2502      lea      0x4(%rax,%rcx,4),%rsi \/\/ rsi = first + length \/ 2 + 1 10.14 \u2502      cmova    %rsi,%rax             \/\/ first = compare_res ? first : rsi  4.87 \u2502      cmovbe   %rcx,%rdx             \/\/ rdx = not compare_res ? length \/ 2 : rdx  0.88 \u2502      mov      %rdx,%rsi             \/\/ rsi = rdx (\u043d\u043e\u0432\u0430\u044f \u0434\u043b\u0438\u043d\u0430)  0.33 \u2502      test     %rdx,%rdx             \/\/ \u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c FLAGS \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438 rdx  3.90 \u2502    \u2191 jg       20                    \/\/ \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u043a\u043e\u043c\u0430\u043d\u0434\u0435 20, \u0435\u0441\u043b\u0438 rdx \u043d\u0435 \u0440\u0430\u0432\u043d\u043e \u043d\u0443\u043b\u044e  \/\/ sb_lower_bound, clang -cmov, \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0439 \u043a\u043e\u0434 \u0441\u0430\u043c\u043e\u0433\u043e \u0433\u043e\u0440\u044f\u0447\u0435\u0433\u043e \u0446\u0438\u043a\u043b\u0430  4.21 \u250220:   shr      %rcx                  \/\/ rcx = length \/ 2  4.70 \u2502      and      $0x1,%esi             \/\/ esi = length % 2  5.00 \u2502      add      %rcx,%rsi             \/\/ rsi = length \/ 2 + length % 2 68.86 \u2502      vucomiss (%rax,%rcx,4),%xmm0   \/\/ \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c first[rcx] \u0441 value, \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c FLAGS  0.01 \u2502      lea      (%rax,%rsi,4),%rdx    \/\/ rdx = first + length \/ 2 + length % 2 11.69 \u2502      cmova    %rdx,%rax             \/\/ first = compare_res ? first : rdx  3.71 \u2502      mov      %rcx,%rsi             \/\/ rsi = length \/ 2       \u2502      test     %rcx,%rcx             \/\/ \u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c FLAGS \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438 rcx  0.02 \u2502    \u2191 jne      20                    \/\/ \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u043a\u043e\u043c\u0430\u043d\u0434\u0435 20, \u0435\u0441\u043b\u0438 rcx \u043d\u0435 \u0440\u0430\u0432\u043d\u043e \u043d\u0443\u043b\u044e  \/\/ branchless_lower_bound, clang -cmov, \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0439 \u043a\u043e\u0434 \u0441\u0430\u043c\u043e\u0433\u043e \u0433\u043e\u0440\u044f\u0447\u0435\u0433\u043e \u0446\u0438\u043a\u043b\u0430  3.04 \u250270:   lea      (%rdi,%rcx,4),%rax    \/\/ rax = first + length 71.22 \u2502      vucomiss (%rdi,%rcx,4),%xmm0   \/\/ \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c first[rcx] \u0441 value, \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c FLAGS 12.26 \u2502      cmova    %rax,%rdi             \/\/ first = compare_res ? first : rax  1.03 \u25027d:   shr      %rcx                  \/\/ length \/= 2, \u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0441\u0442\u043e\u0438\u0442 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0437\u0434\u0435\u0441\u044c \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u044e\u0442\u0441\u044f FLAGS  1.64 \u2502    \u2191 jne      70                    \/\/ \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u043a\u043e\u043c\u0430\u043d\u0434\u0435 20, \u0435\u0441\u043b\u0438 length \u043d\u0435 \u0440\u0430\u0432\u043d\u043e \u043d\u0443\u043b\u044e<\/code><\/pre>\n<p>  \u0410\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0439 \u043a\u043e\u0434 <code>branchless_lower_bound<\/code> \u043e\u0447\u0435\u043d\u044c \u043a\u043e\u0440\u043e\u0442\u043a\u0438\u0439 \u0438 \u043f\u043e\u043d\u044f\u0442\u043d\u044b\u0439. \u0425\u043e\u0442\u044f \u044d\u0442\u043e \u0445\u043e\u0440\u043e\u0448\u0438\u0439 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438, <code>sb_lower_bound<\/code> \u0432\u044b\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 \u0432 \u0442\u0435\u0441\u0442\u0430\u0445 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438\u0437-\u0437\u0430 \u043d\u0438\u0437\u043a\u0438\u0445 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0442\u0440\u0430\u0442.<\/p>\n<h2><font color=\"#3AC1EF\">\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/font><\/h2>\n<p>  \u0415\u0441\u043b\u0438 \u0432 \u0441\u0430\u043c\u043e\u0439 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0432\u0430\u0448\u0435\u0439 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u0435\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u0438\/\u0438\u043b\u0438 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440 \u043d\u0435 \u0441\u043c\u043e\u0436\u0435\u0442 \u0441\u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0439\u0442\u0435 clang \u0441 <code>-mllvm -x86-cmov-converter=false<\/code> (\u0435\u0441\u043b\u0438 \u0432\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442\u0435 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u043e\u043c x86).<\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0432\u044b \u0432\u044b\u0438\u0433\u0440\u0430\u0435\u0442\u0435 \u043e\u0442 \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430, \u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0439\u0442\u0435 <code>sb_lower_bound<\/code> (\u0438\u043b\u0438 \u0434\u043b\u044f gcc \u043c\u043e\u0436\u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c <a href=\"https:\/\/github.com\/mh-dm\/sb_lower_bound\/blob\/master\/sbm_lower_bound.h\"><code>sbm_lower_bound<\/code><\/a>). \u041a\u043e\u0434 \u044f \u0441\u0434\u0435\u043b\u0430\u043b \u043e\u043f\u0435\u043d\u0441\u043e\u0440\u0441\u043d\u044b\u043c \u0441 \u043b\u0438\u0446\u0435\u043d\u0437\u0438\u0435\u0439 MIT.<\/p>\n<p>  \u041a\u043e\u0434 \u0432\u043c\u0435\u0441\u0442\u0435 \u0441 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0430\u043c\u0438 \u0432\u044b\u043b\u043e\u0436\u0435\u043d \u0437\u0434\u0435\u0441\u044c: <a href=\"https:\/\/github.com\/mh-dm\/sb_lower_bound\/\">github.com\/mh-dm\/sb_lower_bound\/<\/a>.<\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0443 \u0432\u0430\u0441 \u0435\u0441\u0442\u044c \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u0438\u0434\u0435\u0438, \u043c\u044b\u0441\u043b\u0438 \u0438\u043b\u0438 \u0434\u043e\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f, \u0442\u043e \u043c\u043e\u0436\u0435\u0442\u0435 \u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0439 <a href=\"https:\/\/www.reddit.com\/r\/cpp\/comments\/14okto7\/fastest_branchless_binary_search\/\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<h2><font color=\"#3AC1EF\">\u0414\u043e\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435<\/font><\/h2>\n<p>  \u0412 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445 <a href=\"https:\/\/orlp.net\">\u0430\u0432\u0442\u043e\u0440 orlp.net<\/a> \u0441\u043e\u043e\u0431\u0449\u0438\u043b, \u0447\u0442\u043e <code>sb_lower_bound<\/code> \u043c\u043e\u0436\u043d\u043e \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043e\u0442\u0440\u0435\u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0445 \u043a\u043e\u043c\u0430\u043d\u0434 \u0432 \u0433\u043e\u0440\u044f\u0447\u0435\u043c \u0446\u0438\u043a\u043b\u0435 \u0441 9 \u0434\u043e 8.<\/p>\n<pre><code class=\"cpp\">\/\/ sb_lower_bound \u0441 \u0440\u0435\u0444\u0430\u043a\u0442\u043e\u0440\u0438\u043d\u0433\u043e\u043c auto length = last - first; while (length > 0) {    auto half = length \/ 2;    if (comp(first[half], value)) {       \/\/ length - half \u0440\u0430\u0432\u043d\u043e half + length % 2       first += length - half;    }    length = half; } return first;<\/code><\/pre>\n<p>  \u041f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 <code>clang -cmov<\/code> \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u0435, \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0441\u043d\u0438\u0436\u0430\u0435\u0442\u0441\u044f \u0441 33 \u043d\u0441 \u0434\u043e 32 \u043d\u0441.<\/p>\n<h3><font color=\"#3AC1EF\">\u258d \u041f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0432\u044b\u0431\u043e\u0440\u043a\u0430<\/font><\/h3>\n<p>  \u0422\u0430\u043a\u0436\u0435 \u0432 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445 \u043f\u043e\u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u043e\u0432\u0430\u043b\u0438 \u043c\u0435\u0442\u043e\u0434\u0438\u043a\u0443 \u0435\u0449\u0451 \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 (prefetching). \u041f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0432\u044b\u0431\u043e\u0440\u043a\u0430 \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u0442 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0435 \u0447\u0430\u0441\u0442\u0438 \u043f\u0430\u043c\u044f\u0442\u0438 \u0432 \u043a\u044d\u0448 (\u043e\u0431\u044b\u0447\u043d\u043e L1\/L2), \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043a\u043e\u0433\u0434\u0430 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0443\u0436\u043d\u044b, \u0442\u043e \u0437\u0430\u0433\u0440\u0443\u0437\u043a\u0430 \u0434\u043b\u0438\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u0440\u0435\u043c\u044f \u0437\u0430\u0434\u0435\u0440\u0436\u043a\u0438 \u043a\u044d\u0448\u0430 L1\/L2 (\u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e 4\/12 \u0442\u0430\u043a\u0442\u043e\u0432), \u0430 \u043d\u0435 \u0432\u0440\u0435\u043c\u044f \u0431\u043e\u043b\u0435\u0435 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043a\u044d\u0448\u0430 (L3, \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e 40 \u0442\u0430\u043a\u0442\u043e\u0432) \u0438\u043b\u0438 \u043f\u0430\u043c\u044f\u0442\u0438 (\u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e 200 \u0442\u0430\u043a\u0442\u043e\u0432). <a href=\"https:\/\/www.7-cpu.com\/cpu\/Skylake.html\">\u041f\u0440\u0438\u043c\u0435\u0440\u044b \u0442\u0430\u0439\u043c\u0438\u043d\u0433\u043e\u0432<\/a>. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 <code>__builtin_prefetch()<\/code> \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u043c\u0430\u044f \u0438 gcc, \u0438 clang.<\/p>\n<p>  \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u043c\u044b \u0441\u043e\u0431\u0438\u0440\u0430\u0435\u043c\u0441\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0441 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 <code>length \/ 2<\/code>. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0432\u044b\u0431\u043e\u0440\u043a\u0443 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 <code>length \/ 4<\/code> \u0438 <code>length * 3 \/ 4<\/code>. \u0418\u043b\u0438 \u0442\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0432\u044b\u0431\u043e\u0440\u043a\u0443 \u0441 \u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c <code>length \/ 8<\/code>, \u0447\u0442\u043e \u0434\u0430\u0451\u0442 4 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043c\u0435\u0441\u0442\u0430 \u0432 \u043f\u0430\u043c\u044f\u0442\u0438. \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043f\u043e <code>length \/ 4<\/code> \u043e\u0434\u0438\u043d \u0438\u0437 \u043a\u0430\u0436\u0434\u044b\u0445 \u0434\u0432\u0443\u0445 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u0431\u0440\u043e\u0448\u0435\u043d, \u0443\u0434\u0432\u0430\u0438\u0432\u0430\u044f \u043d\u0430\u0433\u0440\u0443\u0437\u043a\u0443 \u043d\u0430 \u043a\u044d\u0448. \u0415\u0441\u043b\u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 <code>length \/ 8<\/code>, \u0442\u043e \u0432\u043f\u0443\u0441\u0442\u0443\u044e \u0431\u0443\u0434\u0443\u0442 \u0432\u044b\u0431\u0440\u043e\u0448\u0435\u043d\u044b \u043f\u044f\u0442\u044c \u0438\u0437 \u043a\u0430\u0436\u0434\u044b\u0445 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0422\u0430\u043a\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0437\u0430\u0442\u0440\u0430\u0442\u044b \u043d\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439 \u0438 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0432\u044b\u0431\u043e\u0440\u043a\u0443, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u0443\u0434\u0443\u0442 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0432 \u0433\u043e\u0440\u044f\u0447\u0435\u043c \u0446\u0438\u043a\u043b\u0435, \u043d\u0430\u0434 \u0443\u043a\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u043d\u0438\u0435\u043c \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043c\u044b \u0442\u0430\u043a \u0443\u043f\u043e\u0440\u043d\u043e \u0442\u0440\u0443\u0434\u0438\u043b\u0438\u0441\u044c.<\/p>\n<p>  \u041d\u0430\u043a\u043e\u043d\u0435\u0446, \u0435\u0441\u043b\u0438 \u043c\u044b \u0443\u0436\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u043b\u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u043b\u043d\u044b\u0445 \u043f\u043e\u0438\u0441\u043a\u043e\u0432, \u0442\u043e \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0435 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f, \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e, \u0443\u0436\u0435 \u0431\u0443\u0434\u0443\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u043a\u044d\u0448\u0435, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0432 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043a\u044d\u0448\u0438 L2 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c 256\u041a\u0411 \u0438 \u0431\u043e\u043b\u0435\u0435 \u043c\u043e\u0436\u0435\u0442 \u0432\u043c\u0435\u0441\u0442\u0438\u0442\u044c\u0441\u044f \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/p>\n<p>  \u041f\u0440\u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0435 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0439 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0432\u044b\u0431\u043e\u0440\u043e\u043a, \u043a\u0430\u043a \u043c\u044b \u0438 \u043e\u0436\u0438\u0434\u0430\u043b\u0438, \u043d\u0438 \u043e\u0434\u043d\u0430 \u043d\u0435 \u043f\u043e\u043c\u043e\u0433\u043b\u0430 \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u043c\u0438 \u043c\u0435\u043d\u0435\u0435 256 \u041a\u0411. \u0412\u043e\u0442 <code>sb_lower_bound<\/code>, \u043d\u043e \u0441 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0439 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u043e\u0439 \u0434\u043b\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u043e\u0442 256 \u041a\u0411:<\/p>\n<pre><code class=\"cpp\">\/\/ sbp_lower_bound auto length = last - first; \/\/ \u0420\u0430\u0437\u043c\u0435\u0440 \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u043d \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u043e\u043c\u0435\u0449\u0430\u0442\u044c\u0441\u044f \u0432 \u043a\u044d\u0448 L2 constexpr int entries_per_256KB = 256 * 1024 \/ sizeof(T); if (length >= entries_per_256KB) {    constexpr int num_per_cache_line = std::max(64 \/ int(sizeof(T)), 1);    while (length >= 3 * num_per_cache_line) {       auto half = length \/ 2;       __builtin_prefetch(&amp;first[half \/ 2]);       \/\/ length - half \u0440\u0430\u0432\u043d\u043e half + length % 2       auto first_half1 = first + (length - half);       __builtin_prefetch(&amp;first_half1[half \/ 2]);       first = comp(first[half], value) ? first_half1 : first;       length = half;    } } while (length > 0) {    auto half = length \/ 2;    auto first_half1 = first + (length - half);    first = comp(first[half], value) ? first_half1 : first;    length = half; } return first;<\/code><\/pre>\n<p>  \u041f\u0440\u0438 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438, \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e\u043c \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u043c\u0443 \u0440\u0430\u043d\u0435\u0435, \u0434\u043b\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u0432 \u0432 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0435 \u0434\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e 4 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0437\u0430\u043f\u0438\u0441\u0435\u0439 (\u0438\u043b\u0438 16 \u041c\u0411) \u0441\u0440\u0435\u0434\u043d\u044f\u044f \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0441\u043d\u0438\u0436\u0430\u0435\u0442\u0441\u044f \u0441 32 \u043d\u0441 \u0434\u043e 26 \u043d\u0441. \u0417\u0434\u0435\u0441\u044c \u044f \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u0438\u0437\u043d\u0430\u0442\u044c, \u0447\u0442\u043e \u043c\u043e\u044f \u0438\u0441\u0445\u043e\u0434\u043d\u0430\u044f \u0442\u043e\u0447\u043a\u0430 \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0430 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u0432 \u043e\u043a\u0430\u0437\u0430\u043b\u0430\u0441\u044c \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0439. \u0422\u0430\u043a \u0447\u0442\u043e \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0437\u0430\u0431\u0435\u0440\u0451\u043c\u0441\u044f \u0433\u043e\u0440\u0430\u0437\u0434\u043e \u0432\u044b\u0448\u0435, \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0434\u043e 128 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0437\u0430\u043f\u0438\u0441\u0435\u0439 (\u0438\u043b\u0438 512 \u041c\u0411). \u042d\u0442\u043e \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c L3, \u043d\u043e \u0432\u0441\u0451 \u0440\u0430\u0432\u043d\u043e \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0440\u0430\u0437\u0443\u043c\u043d\u044b\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u043d\u0430\u0431\u043e\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n<p>  \u0412\u0440\u0435\u043c\u044f \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0432 \u0432\u0438\u0434\u0435 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0433\u0440\u0430\u0444\u0438\u043a\u043e\u0432:<\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/dn\/6w\/pg\/dn6wpglsfc2qskg9bwdhdoh0b2o.png\" data-src=\"https:\/\/habrastorage.org\/webt\/dn\/6w\/pg\/dn6wpglsfc2qskg9bwdhdoh0b2o.png\"\/><\/div>\n<p>  \u041f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0435 \u0432\u0435\u0449\u0438.<\/p>\n<ul>\n<li><code>std::lower_bound<\/code> \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 <code>clang -cmov<\/code>, \u043f\u0440\u0438 \u043e\u0433\u0440\u043e\u043c\u043d\u044b\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u0430\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u0432\u0435\u0440\u0441\u0438\u044f \u0441 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0435\u043c. \u0421\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 CPU \u0441\u043b\u0435\u0434\u0443\u044e\u0442 \u043f\u043e \u0441\u043f\u0440\u043e\u0433\u043d\u043e\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f\u043c, \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442 \u0437\u0430\u0433\u0440\u0443\u0437\u043a\u0443 \u0438\u0437 \u043f\u0430\u043c\u044f\u0442\u0438 (\u043f\u043e \u0441\u0443\u0442\u0438, \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0432\u044b\u0431\u043e\u0440\u043a\u0443), \u0438 \u0441\u043f\u0435\u043a\u0443\u043b\u044f\u0442\u0438\u0432\u043d\u043e \u043f\u0440\u043e\u0432\u043e\u0434\u044f\u0442 \u0440\u0430\u0431\u043e\u0442\u0443 \u0441 \u044d\u0442\u0438\u043c\u0438 \u0434\u0430\u043d\u043d\u044b\u043c\u0438 (\u043f\u043e \u0441\u0443\u0442\u0438 \u044d\u0442\u043e <a href=\"https:\/\/en.wikipedia.org\/wiki\/Transient_execution_CPU_vulnerability\">\u043a\u043e\u0448\u043c\u0430\u0440 \u0434\u043b\u044f \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u0438<\/a>).<\/li>\n<li><code>sbpm_lower_bound<\/code> \u2014 \u044d\u0442\u043e \u0432\u0435\u0440\u0441\u0438\u044f <code>sbm_lower_bound<\/code> \u0441 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u043e\u0439, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0443\u043c\u043d\u043e\u0436\u0430\u0435\u0442\u0441\u044f \u043d\u0430 boolean, \u0447\u0442\u043e\u0431\u044b \u0445\u0438\u0442\u0440\u043e\u0441\u0442\u044c\u044e \u0437\u0430\u0441\u0442\u0430\u0432\u0438\u0442\u044c gcc \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u043e\u0434 \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f.<\/li>\n<li>\u041f\u0440\u0438 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 <code>std::lower_bound<\/code> (161 \u043d\u0441) \u0438 \u0432\u0435\u0440\u0441\u0438\u0438 \u0441 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u043e\u0439 (71 \u043d\u0441) \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0432 2,3 \u0440\u0430\u0437\u0430.<\/li>\n<\/ul>\n<p>  <\/p>\n<h3><font color=\"#3AC1EF\">\u258d \u0411\u044b\u0441\u0442\u0440\u0435\u0435?<\/font><\/h3>\n<p>  <\/p>\n<h4><font color=\"#3AC1EF\">\u258d \u0412\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c\u0430\u044f \u0437\u0430\u043c\u0435\u043d\u0430 \u0434\u043b\u044f std::lower_bound<\/font><\/h4>\n<p>  \u041d\u0430 \u0433\u0440\u0430\u0444\u0438\u043a\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0435\u0441\u0442\u044c \u0432\u0441\u043f\u043b\u0435\u0441\u043a\/\u0430\u043d\u043e\u043c\u0430\u043b\u0438\u044f \u0432 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0435 1-10 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0442\u0430\u043a \u0447\u0442\u043e \u0432 \u0442\u0435\u043e\u0440\u0438\u0438 \u043e\u043d\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043a\u043e\u0434 \u0441 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u043e\u0439 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u0445\u0430\u043e\u0442\u0438\u0447\u043d\u044b\u043c \u0438 \u0432 \u043d\u0451\u043c \u043f\u043e\u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0432\u043e\u043b\u0448\u0435\u0431\u043d\u044b\u0435 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b. \u0412 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0441\u0442\u0430 \u0443 \u043c\u0435\u043d\u044f \u0431\u044b\u043b\u0430 \u0432\u043e\u0441\u0445\u0438\u0442\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f (\u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0430\u044f) \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u043d\u0435\u0441\u0442\u0438 \u0432\u043a\u043b\u0430\u0434 \u0432 <a href=\"https:\/\/gcc.gnu.org\/contribute.html\">gcc\/libstdc++<\/a> \u0438\/\u0438\u043b\u0438 <a href=\"https:\/\/libcxx.llvm.org\/Contributing.html\">llvm\/libc++<\/a>. \u042f \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u044e\u0441\u044c \u043d\u0430 \u044d\u0442\u043e\u043c, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u0435\u0449\u0451 \u043c\u0435\u043d\u044c\u0448\u0435 \u0441 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438.<\/p>\n<h4><font color=\"#3AC1EF\">\u258d \u041b\u043e\u043c\u0430\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f std::lower_bound<\/font><\/h4>\n<p>  \u0412 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445 \u0442\u0430\u043a\u0436\u0435 \u0443\u043f\u043e\u043c\u044f\u043d\u0443\u043b\u0438 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 <a href=\"https:\/\/algorithmica.org\/en\/eytzinger\">\u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u042d\u0439\u0442\u0446\u0438\u043d\u0433\u0435\u0440\u0430<\/a>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u0435\u0442\u0441\u044f (\u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u0443\u044e \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u0443\u044e \u00ab\u043a\u0443\u0447\u0443\u00bb), \u0447\u0442\u043e\u0431\u044b \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u044b\u043b\u0438 \u0443\u0434\u043e\u0431\u043d\u044b \u0434\u043b\u044f \u043a\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u042f \u043c\u043e\u0433 \u0431\u044b \u043f\u043e\u0434\u0443\u043c\u0430\u0442\u044c, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0431\u044b\u0441\u0442\u0440\u044b\u043c\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c SIMD-\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 K-\u0438\u0447\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u043d\u043e \u0440\u0430\u0437\u043c\u044b\u0448\u043b\u044f\u0442\u044c \u043e\u0431 \u044d\u0442\u043e\u043c \u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u043b\u043e\u0441\u044c: \u043e\u0442 7 \u0434\u043e 15 \u0440\u0430\u0437 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c <code>std::lower_bound<\/code> (16-\u0438\u0447\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 int), \u043a\u0430\u043a \u043f\u043e\u043a\u0430\u0437\u0430\u043b <a href=\"https:\/\/www.youtube.com\/watch?v=1RIPMQQRBWk\">\u0421\u0435\u0440\u0433\u0435\u0439 \u0421\u043b\u043e\u0442\u0438\u043d \u043d\u0430 CppCon 2022<\/a>.<a name=\"1\"><\/a><\/p>\n<h2><font color=\"#3AC1EF\">\u0421\u0441\u044b\u043b\u043a\u0438<\/font><\/h2>\n<p>  <\/p>\n<ol>\n<li><a name=\"2\"><\/a>\u0410 \u0412\u041e\u0422 RUST\u2026 Rust \u0431\u044b\u0441\u0442\u0440\u044b\u0439, \u043d\u043e \u0432\u044b \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0445\u043e\u0442\u0435\u043b\u0438 \u0431\u044b, \u0447\u0442\u043e\u0431\u044b \u043c\u043e\u0439 \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0441\u0442 \u0431\u044b\u043b \u043f\u043e\u0441\u0432\u044f\u0449\u0451\u043d <a href=\"https:\/\/doc.rust-lang.org\/1.71.1\/src\/core\/slice\/mod.rs.html#2767\">unsafe-\u043a\u043e\u0434\u0443<\/a>?<a name=\"3\"><\/a><\/li>\n<li>\u0410 \u0412\u041e\u0422 ZIG\u2026 \u0412 Zig \u043d\u0435\u0442 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0430\u043f\u043e\u0434\u043e\u0431\u0438\u0435 <code>lower_bound()<\/code>, \u0442\u043e\u043b\u044c\u043a\u043e <a href=\"https:\/\/ziglang.org\/documentation\/master\/std\/#A;std:sort.binarySearch\">\u0432\u043e\u0442 \u044d\u0442\u043e<\/a>.<a name=\"4\"><\/a><\/li>\n<li>\u0412\u0441\u0435\u0433\u0434\u0430 \u0435\u0441\u0442\u044c <a href=\"https:\/\/xkcd.ru\/149\/\">\u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0439 XKCD<\/a>.<a name=\"5\"><\/a><\/li>\n<li>\u041f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 clang \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c <a href=\"https:\/\/clang.llvm.org\/docs\/LanguageExtensions.html#builtin-unpredictable\"><code>__builtin_unpredictable<\/code><\/a><code>(comp(first[half], value))<\/code>, \u043d\u043e \u044d\u0442\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0434\u0430\u0451\u0442 (\u043f\u0440\u043e\u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043e \u043d\u0430 v10-13).<\/li>\n<li>\u0423 gcc \u0435\u0441\u0442\u044c <a href=\"https:\/\/gcc.gnu.org\/onlinedocs\/gcc\/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect_005fwith_005fprobability\"><code>__builtin_expect_with_probability<\/code><\/a><code>(cond, 0, 0.5)<\/code>, \u043d\u043e \u044d\u0442\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0434\u0430\u0451\u0442 (\u043f\u0440\u043e\u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043e \u043d\u0430 v10).<\/li>\n<\/ol>\n<p>  <\/p>\n<blockquote><p><b><font color=\"#3AC1EF\"><a href=\"https:\/\/t.me\/ruvds_community\">Telegram-\u043a\u0430\u043d\u0430\u043b \u0441 \u0440\u043e\u0437\u044b\u0433\u0440\u044b\u0448\u0430\u043c\u0438 \u043f\u0440\u0438\u0437\u043e\u0432, \u043d\u043e\u0432\u043e\u0441\u0442\u044f\u043c\u0438 IT \u0438 \u043f\u043e\u0441\u0442\u0430\u043c\u0438 \u043e \u0440\u0435\u0442\u0440\u043e\u0438\u0433\u0440\u0430\u0445 ?\ufe0f<\/a><\/font><\/b><\/p><\/blockquote>\n<p><a href=\"http:\/\/ruvds.com\/ru-rub?utm_source=habr&amp;utm_medium=article&amp;utm_campaign=ru_vds&amp;utm_content=bystryj_dvoichnyj_poisk_bez_vetvleniya\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/_p\/_h\/lv\/_p_hlvd2tv0cv9tny8tdytzfhje.png\" data-src=\"https:\/\/habrastorage.org\/webt\/_p\/_h\/lv\/_p_hlvd2tv0cv9tny8tdytzfhje.png\"\/><\/a><\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/756422\/\"> https:\/\/habr.com\/ru\/articles\/756422\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\"><a href=\"https:\/\/habr.com\/ru\/companies\/ruvds\/articles\/756422\/\"><\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/s0\/mp\/j5\/s0mpj5nfcn1lrqfw1k3yt56f4b8.png\" data-src=\"https:\/\/habrastorage.org\/webt\/s0\/mp\/j5\/s0mpj5nfcn1lrqfw1k3yt56f4b8.png\"\/><\/div>\n<p><\/a><br \/>  \u041c\u043e\u0438 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0438 \u2014 \u0437\u0430\u043d\u044f\u0442\u044b\u0435 \u043b\u044e\u0434\u0438, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0440\u0430\u0437\u0443 \u043f\u0435\u0440\u0435\u0439\u0434\u0443 \u043a \u0434\u0435\u043b\u0443. \u0412\u043e\u0442 \u043e\u043d\u0430, \u0441\u0430\u043c\u0430\u044f \u0431\u044b\u0441\u0442\u0440\u0430\u044f \u043e\u0431\u043e\u0431\u0449\u0451\u043d\u043d\u0430\u044f (\u0438 \u043f\u0440\u043e\u0441\u0442\u0430\u044f) \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0430 C++:<\/p>\n<pre><code class=\"cpp\">template &lt;class ForwardIt, class T, class Compare> constexpr ForwardIt sb_lower_bound(       ForwardIt first, ForwardIt last, const T&amp; value, Compare comp) {    auto length = last - first;    while (length > 0) {       auto rem = length % 2;       length \/= 2;       if (comp(first[length], value)) {          first += length + rem;       }    }    return first; }<\/code><\/pre>\n<p>  \u0422\u043e\u0442 \u0436\u0435 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u0447\u0442\u043e \u0438 \u0443 <code>std::lower_bound<\/code>, \u043d\u043e <strong><font color=\"#3AC1EF\">\u0432\u0434\u0432\u043e\u0435<\/font><\/strong> \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438 \u043a\u043e\u0440\u043e\u0447\u0435. \u00ab\u0411\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f\u00bb, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e <code>if<\/code> \u043a\u043e\u043c\u043f\u0438\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u043c\u0430\u043d\u0434\u0443 \u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0438, \u0430 \u043d\u0435 \u0432 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u0435\/\u0443\u0441\u043b\u043e\u0432\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0445\u043e\u0434. \u0411\u043b\u0438\u0436\u0435 \u043a \u043a\u043e\u043d\u0446\u0443 \u0441\u0442\u0430\u0442\u044c\u0438 \u043c\u044b \u0438\u0437\u0443\u0447\u0438\u043c \u043e\u043f\u0446\u0438\u0438 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430 \u0438 \u0434\u0430\u0436\u0435 \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u044b\u0435 \u0432\u0435\u0440\u0441\u0438\u0438 \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0431\u0435\u0437 \u0432\u0435\u0442\u0432\u043b\u0435\u043d\u0438\u044f. \u0414\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 \u043d\u0435 \u043d\u0443\u0436\u043d\u044b \u043e\u0441\u043e\u0431\u044b\u0435 \u0437\u043d\u0430\u043d\u0438\u044f \u0432 C++. \u0414\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c, \u0447\u0442\u043e \u0438\u0442\u0435\u0440\u0430\u0442\u043e\u0440\u044b (<code>first<\/code> \u0438 <code>last<\/code>) \u043f\u043e \u0441\u0443\u0442\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f\u043c\u0438 \u043d\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0445\u043e\u0442\u044f \u043c\u043e\u0433\u0443\u0442 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u043d\u0430 \u043e\u0434\u0438\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u0430\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u041c\u043e\u0436\u0435\u0442\u0435 \u043d\u0435 \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u043d\u0430 <code>template<\/code>, <code>class<\/code>, <code>constexpr<\/code> \u0438 <code>&amp;<\/code>. \u0412\u043e\u0442 \u0435\u0441\u043b\u0438 \u0431\u044b \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043b \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438 \u0447\u0438\u0441\u0442\u044b\u0439 \u044f\u0437\u044b\u043a, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0439 \u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 \u0436\u0435\u043b\u0435\u0437\u0430&#8230;<sup><a href=\"#1\">1<\/a><\/sup> <sup><a href=\"#2\">2<\/a><\/sup><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-352956","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/352956","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=352956"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/352956\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=352956"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=352956"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=352956"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}