Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бинарлық арифметикалық алгоритм
Binary arithmetic algorithm
Компьютерлік бағдарламалауда, эксклюзивті немесе алмастыру (кейде XOR алмастыру деп қысқартылады) – екі айнымалының мәндерін уақытша айнымалы қолданбай алмастыру үшін эксклюзивті немесе биттік операциясын пайдаланатын алгоритм. Алгоритм көбінесе жаңалық ретінде және эксклюзивті немесе операциясының қасиеттерін көрсету тәсілі ретінде қолданылады. Ол кейде бағдарламаны оңтайландыру ретінде талқыланады, бірақ эксклюзивті немесе арқылы алмастыру стандартты, түсінікті тәсілге қарағанда көбінесе артықшылық бермейді.
In computer programming, the exclusive or swap (sometimes shortened to XOR swap) is an algorithm that uses the exclusive or bitwise operation to swap the values of two variables without using the temporary variable which is normally required. The algorithm is primarily a novelty and a way of demonstrating properties of the exclusive or operation. It is sometimes discussed as a program optimization, but there are almost no cases where swapping via exclusive or provides benefit over the standard, obvious technique.
Іс жүзінде аулақ болу себептері
Қазіргі заманғы CPU архитектураларында XOR техникасы уақытша айнымалы қолданып ауыстырудан баяу болуы мүмкін. Кем дегенде, AMD және Intel компанияларының соңғы x86 процессорларында тіркелімдер арасындағы деректерді жылжыту әдетте кідіріс тудырмайды. (Бұл MOV жою деп аталады.) Егер қолдануға архитектуралық тіркелімдер жетпесе де, XCHG командасы үш XOR операциясынан кем емес жылдамдықпен орындалады. Тағы бір себеп – қазіргі заманғы процессорлар нұсқау құбырлары арқылы нұсқауларды параллель түрде орындауға ұмтылады. XOR техникасында әрбір операцияның нәтижесі алдыңғы операцияның нәтижесіне байланысты болғандықтан, оларды қатаң тізбекпен орындау қажет, бұл нұсқау деңгейіндегі параллелизмнің артықшылықтарын жояды.
On modern CPU architectures, the XOR technique can be slower than using a temporary variable to do swapping. At least on recent x86 CPUs, both by AMD and Intel, moving between registers regularly incurs zero latency. (This is called MOV elimination.) Even if there is not any architectural register available to use, the XCHG instruction will be at least as fast as the three XORs taken together. Another reason is that modern CPUs strive to execute instructions in parallel via instruction pipelines. In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order, negating any benefits of instruction level parallelism.
Аталық атауы
XOR алмасуы практикада псевдонимдердің болуымен де қиындатылады. Егер XOR көмегімен қандай да бір жад орынының мазмұнын өзімен алмастыруға тырысылса, нәтижесінде ол жад орыны нөлге теңеліп, оның мәні жоғалады. Сондықтан, егер псевдонимдер пайда болу мүмкіндігі болса, жоғары деңгейдегі бағдарламалау тілінде XOR алмасуын сақтықсыз қолдануға болмайды. Егер бұл техника екі тіркегіштің мазмұнын алмастыру үшін құрастыру тілінде қолданылса, бұл мәселе туындамайды. Дженсеннің құрылғысындағы i және A[i] айнымалыларын уақытша айнымалы арқылы алмастыру, аргументтердің байланысты болуына байланысты дұрыс емес нәтижелерге әкеледі: temp = i; i = A[i]; A[i] = temp түріндегі алмастыру екінші операторда i-нің мәнін өзгертеді, ал үшінші операторда A[i] үшін бұрыс i мәнін пайдалануға себеп болады.
The XOR swap is also complicated in practice by aliasing. If an attempt is made to XOR swap the contents of some location with itself, the result is that the location is zeroed out and its value lost. Therefore, XOR swapping must not be used blindly in a high level language if aliasing is possible. This issue does not apply if the technique is used in assembly to swap the contents of two registers. Similar problems occur with call by name, as in Jensen's Device, where swapping i and A[i] via a temporary variable yields incorrect results due to the arguments being related: swapping via temp = i; i = A[i]; A[i] = temp changes the value for i in the second statement, which then results in the incorrect i value for A[i] in the third statement.
Бөлшектерді тіркеу туралы өтініш
Арнайы алмасу нұсқаулығы жоқ архитектураларда, себебі ол қосымша уақытша тіркеуішті пайдалануды болдырмайды, оптималды тіркеуіштерді бөлу үшін XOR алмасу алгоритмі қажет. Бұл, әсіресе тіркеуіштерді бөлу үшін статикалық бір тапсырма пішімін пайдаланатын компиляторлар үшін маңызды; мұндай компиляторлар кейде тіркеуіштер бос болмағанда екі тіркеуішті алмастыру қажет болатын бағдарламаларды жасайды. XOR алмасу алгоритмі қосымша тіркеуішті резервте ұстау немесе кез келген тіркеуіштерді негізгі жадқа төгу қажеттілігін болдырмайды. Қосу/азайту түрі де осы мақсатта қолданылуы мүмкін. Бұл әдіс, әсіресе GPU шейдер компиляторлары үшін маңызды. Қазіргі заманғы GPU архитектураларында айнымалыларды жадқа төгу, шектеулі жад ені мен жоғары жад кешігуі салдарынан қымбатқа түседі, ал тіркеуіштерді пайдалануды шектеу тіркеуіштер файлын динамикалық бөлу арқылы өнімділікті арттыруға мүмкіндік береді. Сондықтан кейбір GPU компиляторлары XOR алмасу алгоритмін қажет етеді.
On architectures lacking a dedicated swap instruction, because it avoids the extra temporary register, the XOR swap algorithm is required for optimal register allocation. This is particularly important for compilers using static single assignment form for register allocation; these compilers occasionally produce programs that need to swap two registers when no registers are free. The XOR swap algorithm avoids the need to reserve an extra register or to spill any registers to main memory. The addition/subtraction variant can also be used for the same purpose. This method of register allocation is particularly relevant to GPU shader compilers. On modern GPU architectures, spilling variables is expensive due to limited memory bandwidth and high memory latency, while limiting register usage can improve performance due to dynamic partitioning of the register file. The XOR swap algorithm is therefore required by some GPU compilers.